Given an array of integers arr and two integers k and threshold, return the number of sub-arrays of size k and average greater than or equal to threshold.
Example 1:
Input: arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4 Output: 3 Explanation: Sub-arrays [2,5,5],[5,5,5] and [5,5,8] have averages 4, 5 and 6 respectively. All other sub-arrays of size 3 have averages less than 4 (the threshold).
Example 2:
Input: arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5 Output: 6 Explanation: The first 6 sub-arrays of size 3 have averages greater than 5. Note that averages are not integers.
Constraints:
1 <= arr.length <= 1051 <= arr[i] <= 1041 <= k <= arr.length0 <= threshold <= 104Problem Overview: You are given an integer array arr, a window size k, and a threshold. Count how many contiguous subarrays of length k have an average greater than or equal to the threshold. Since the subarray size is fixed, the task reduces to efficiently computing the sum of every window of length k and checking whether sum / k >= threshold.
Approach 1: Brute Force (Time: O(n * k), Space: O(1))
The straightforward method iterates over every possible subarray of length k. For each starting index, compute the sum of the next k elements using a loop, calculate the average, and compare it with the threshold. If the condition holds, increment the result counter. This approach uses no extra memory beyond a few variables, but repeatedly recalculates sums for overlapping windows. When n is large, recomputing each window from scratch becomes inefficient because each element is processed up to k times.
Approach 2: Sliding Window (Time: O(n), Space: O(1))
The optimal approach uses a Sliding Window over the Array. Instead of recomputing sums for each subarray, maintain the sum of the current window of size k. First compute the sum of the initial k elements. Then move the window one step to the right by subtracting the element leaving the window and adding the new element entering the window. Each shift updates the sum in constant time. Check whether windowSum >= k * threshold instead of computing division; this avoids floating-point operations and simplifies comparison.
Because each element enters and leaves the window exactly once, the total work is linear in the size of the array. The algorithm uses only a few variables to track the running sum and the result count, so the extra space remains constant. This technique appears frequently in problems where a fixed-size window moves across an array.
Recommended for interviews: The sliding window solution is the expected answer. Interviewers want to see that you recognize repeated work in overlapping subarrays and replace it with a rolling sum update. Mentioning the brute force approach first demonstrates understanding of the problem, but switching to the sliding window optimization shows algorithmic maturity and familiarity with common patterns like Sliding Window on arrays.
This approach utilizes the sliding window technique to calculate the sum of each sub-array of size k efficiently.
By maintaining a running sum of the current sub-array of size k and updating the sum as the window slides forward, we can avoid recalculating the sum from scratch each time, reducing the time complexity substantially.
The Python solution initializes the current sum with the sum of the first k elements. It uses a loop to subtract the element going out of the current sub-array and add the new element entering the sub-array window. If the resultant sum is greater than or equal to the target sum (k * threshold), the count is incremented.
Time Complexity: O(n) - where n is the length of the array, as the algorithm processes each element once.
Space Complexity: O(1) - no extra space proportional to input size is used.
This approach employs a simple brute force strategy, computing the sum of each sub-array of length k individually and comparing it against the needed threshold multiplied by k.
This approach serves as a baseline for understanding the problem's requirements, though it is not optimal for large input sizes.
The Python brute force solution iterates over all possible k-length sub-arrays, computes their sum individually using the built-in sum function, and increments the count for those that meet or exceed the threshold times k.
Time Complexity: O(nk) - the sum for each sub-array is recomputed in each iteration.
Space Complexity: O(1) - no additional storage other than basic variables is utilized.
We can multiply threshold by k, so that we can directly compare the sum within the window with threshold.
We maintain a sliding window of length k, and for each window, we calculate the sum s. If s is greater than or equal to threshold, we increment the answer.
The time complexity is O(n), where n is the length of the array arr. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Sliding Window Approach | Time Complexity: O(n) - where n is the length of the array, as the algorithm processes each element once. Space Complexity: O(1) - no extra space proportional to input size is used. |
| Brute Force Approach | Time Complexity: O(nk) - the sum for each sub-array is recomputed in each iteration. Space Complexity: O(1) - no additional storage other than basic variables is utilized. |
| Sliding Window | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force | O(n * k) | O(1) | Good for understanding the problem or when constraints are very small |
| Sliding Window | O(n) | O(1) | Optimal approach for fixed-size subarray problems and large inputs |
Number of Subarrays of size K and Average Greater than or Equal to Threshold - Leetcode 1343 Python • NeetCodeIO • 16,165 views views
Watch 9 more video solutions →Practice Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold with our built-in code editor and test cases.
Practice on FleetCode