Leetcode 1343: Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold
Given an array of integers arr and two integers k and threshold, return the number of subarrays of size k whose average is greater than or equal to the threshold.
Problem
Approach
Steps
Complexity
Input: The input consists of an array of integers and two integers, k and threshold.
Example: arr = [1,3,5,7,9,10,12], k = 3, threshold = 7
Constraints:
• 1 <= arr.length <= 10^5
• 1 <= arr[i] <= 10^4
• 1 <= k <= arr.length
• 0 <= threshold <= 10^4
Output: Return the number of subarrays of size k whose average is greater than or equal to the threshold.
Example: For arr = [1,3,5,7,9,10,12], k = 3, threshold = 7, the output will be 4.
Constraints:
• The answer will be a non-negative integer.
Goal: Count how many subarrays of size k have an average greater than or equal to the threshold.
Steps:
• 1. Use a sliding window of size k to calculate the sum of each subarray.
• 2. Compute the average by dividing the sum of the subarray by k.
• 3. Count the number of subarrays whose average is greater than or equal to the threshold.
Goal: The solution should efficiently handle large input sizes.
Steps:
• The number of elements in the array is at most 10^5.
• The values in the array and threshold are bounded by 10^4.
Assumptions:
• The array will always have at least one subarray of the given size k.
• The array elements and threshold are non-negative integers.
• Input: Example 1: arr = [1, 3, 5, 7, 9, 10, 12], k = 3, threshold = 7
• Explanation: Subarrays of size 3 are checked, and their averages are compared to the threshold to count the valid subarrays.
• Input: Example 2: arr = [2, 2, 2, 2, 5, 5, 5, 8], k = 3, threshold = 4
• Explanation: The subarrays are evaluated based on their averages, and only those meeting or exceeding the threshold are counted.
Approach: To solve the problem, we can use a sliding window technique to efficiently compute the sum of each subarray of size k and check if the average is greater than or equal to the threshold.
Observations:
• A sliding window approach ensures we only calculate the sum of each subarray once and adjust it as we move through the array.
• The sliding window approach is efficient and avoids recalculating the sum from scratch for each subarray, making it optimal for large arrays.
Steps:
• 1. Initialize a sum variable for the first k elements of the array.
• 2. Slide the window over the array, adding the next element and subtracting the element that moves out of the window.
• 3. Check if the sum of the current window is greater than or equal to k * threshold.
• 4. Count such windows and return the count.
Empty Inputs:
• There are no empty arrays, as the length of arr is always at least 1.
Large Inputs:
• For large inputs, the solution should be efficient and run in O(n) time where n is the length of the array.
Special Values:
• The threshold value may be 0, in which case all subarrays with positive values will have an average greater than or equal to the threshold.
Constraints:
• The array will contain only positive integers, and the subarray size k will always be valid.
int numOfSubarrays(vector<int>& arr, int k, int th) {
int cnt = 0, sum = 0;
th = th * k;
for(int i = 0; i < k; i++) {
sum += arr[i];
}
cnt += sum >= th;
for(int i = k; i < arr.size(); i++) {
sum += arr[i];
sum -= arr[i - k];
if(sum >= th) cnt++;
}
return cnt;
}
1 : Function Declaration
int numOfSubarrays(vector<int>& arr, int k, int th) {
Defines the function that takes an array, window size `k`, and a threshold value `th` as inputs and returns the count of subarrays meeting the criteria.
2 : Variable Initialization
int cnt = 0, sum = 0;
Initializes `cnt` to track the number of valid subarrays and `sum` to store the current window's sum.
3 : Threshold Adjustment
th = th * k;
Converts the threshold to the total sum equivalent for a subarray of size `k` by multiplying it with `k`.
4 : Initial Window
for(int i = 0; i < k; i++) {
Starts a loop to calculate the sum of the first window of size `k`.
5 : Sum Update
sum += arr[i];
Adds the current element to the sum for the first window.
6 : Initial Count Check
cnt += sum >= th;
Checks if the initial window meets the threshold and increments `cnt` if true.
7 : Sliding Window Loop
for(int i = k; i < arr.size(); i++) {
Begins the sliding window process to check subsequent windows.
8 : Window Update Add
sum += arr[i];
Adds the next element in the array to the current window's sum.
9 : Window Update Remove
sum -= arr[i - k];
Removes the element that is sliding out of the window from the sum.
10 : Count Check
if(sum >= th) cnt++;
Checks if the updated window's sum meets the threshold and increments `cnt` if true.
11 : Return Result
return cnt;
Returns the final count of subarrays meeting the threshold criteria.
Best Case: O(n), where n is the number of elements in the array.
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n) because we only traverse the array once while maintaining a sliding window.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is O(1) since we only need a few extra variables to track the sum and count.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus