Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold

Med

#1247Time: O(N * K), where N is the length of `arr`. The outer loop runs `N - K + 1` times, and for each of these iterations, the inner loop runs `K` times to compute the sum. This results in a quadratic time complexity in the worst case (when K is close to N/2).Space: O(1). We only use a few variables to store the count, sum, and loop indices, which does not depend on the input size.1 company

Patterns

Sliding Window

Data structures

Array

Companies

Turo

Prompt

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 <= 10⁵
1 <= arr[i] <= 10⁴
1 <= k <= arr.length
0 <= threshold <= 10⁴

Approaches

2 approaches with complexity analysis and trade-offs.

The brute-force approach is the most straightforward way to solve the problem. We can generate every possible contiguous subarray of size k, calculate its sum, find the average, and then check if this average is greater than or equal to the given threshold. We use a counter to keep track of how many such subarrays we find.

Algorithm

Initialize a counter count to 0.
Iterate through the array with an index i from 0 up to arr.length - k. This index i will be the starting point of each subarray.
For each i, start a nested loop to iterate from j = i to j = i + k - 1 to traverse the elements of the current subarray.
Calculate the sum of the elements in this subarray.
After calculating the sum, check if the average (sum / k) is greater than or equal to the threshold. To avoid floating-point arithmetic, this is equivalent to checking if sum >= k * threshold.
If the condition is true, increment the count.
After the outer loop finishes, return the count.

Walkthrough

We use a nested loop structure. The outer loop iterates from the beginning of the array to the last possible starting point for a subarray of size k (which is arr.length - k). The inner loop then iterates k times from the starting point determined by the outer loop to calculate the sum of the current subarray's elements.

An important optimization is to avoid floating-point division inside the loop. The condition (sum / k) >= threshold can be rewritten as sum >= k * threshold. This allows us to work entirely with integers (or long, to be safe from overflow, though not strictly necessary with the given constraints).

1class Solution {2    public int numOfSubarrays(int[] arr, int k, int threshold) {3        int count = 0;4        long targetSum = (long) k * threshold;5        int n = arr.length;6 7        // Iterate through all possible starting points of a subarray of size k8        for (int i = 0; i <= n - k; i++) {9            long currentSum = 0;10            // Calculate the sum of the subarray starting at i11            for (int j = i; j < i + k; j++) {12                currentSum += arr[j];13            }14 15            // Check if the average condition is met16            if (currentSum >= targetSum) {17                count++;18            }19        }20        return count;21    }22}

Complexity

Time

O(N * K), where N is the length of `arr`. The outer loop runs `N - K + 1` times, and for each of these iterations, the inner loop runs `K` times to compute the sum. This results in a quadratic time complexity in the worst case (when K is close to N/2).

Space

O(1). We only use a few variables to store the count, sum, and loop indices, which does not depend on the input size.

Trade-offs

Pros

Very simple to understand and implement.
It's a good starting point for understanding the problem.

Cons

This approach is inefficient because it re-calculates the sum of elements for overlapping parts of consecutive subarrays.
For large inputs, this will likely result in a 'Time Limit Exceeded' (TLE) error on coding platforms.

A much more efficient solution uses the sliding window technique. This approach avoids the redundant calculations of the brute-force method. We maintain a 'window' of size k and a running sum of its elements. As we slide this window across the array, we can update the sum in constant time by subtracting the element that's leaving the window and adding the new element that's entering. This reduces the overall time complexity from quadratic to linear.

Algorithm

First, calculate the required sum targetSum = k * threshold to avoid floating-point arithmetic.
Initialize a windowSum by summing the first k elements of the array.
Initialize a counter count to 0.
Check if the initial windowSum is greater than or equal to targetSum. If it is, increment count.
Iterate from index k to the end of the array (i from k to arr.length - 1). This loop slides the window one position at a time.
In each iteration, update windowSum by adding the new element entering the window (arr[i]) and subtracting the element leaving the window (arr[i - k]).
After updating windowSum, check if it's greater than or equal to targetSum. If it is, increment count.
After the loop completes, return the final count.

Walkthrough

The core idea is to maintain the sum of a k-sized window as it slides over the array. We start by computing the sum of the very first subarray (from index 0 to k-1). We check if this initial subarray meets the condition. Then, we iterate from the k-th element to the end of the array. In each step, instead of re-calculating the sum of the new window from scratch, we update the previous sum. The new sum is simply previous_sum - element_leaving_from_left + element_entering_from_right. This update operation takes constant O(1) time. We check the condition for each new window sum and update our count accordingly.

1class Solution {2    public int numOfSubarrays(int[] arr, int k, int threshold) {3        int count = 0;4        long windowSum = 0;5        long targetSum = (long) k * threshold;6        int n = arr.length;7 8        // Calculate the sum of the first window9        for (int i = 0; i < k; i++) {10            windowSum += arr[i];11        }12 13        // Check the first window14        if (windowSum >= targetSum) {15            count++;16        }17 18        // Slide the window across the rest of the array19        for (int i = k; i < n; i++) {20            // Update the window sum in O(1)21            windowSum += arr[i] - arr[i - k];22            23            // Check the new window24            if (windowSum >= targetSum) {25                count++;26            }27        }28 29        return count;30    }31}

Complexity

Time

O(N), where N is the length of `arr`. We perform a single pass to calculate the initial window sum (O(K)) and another single pass to slide the window through the rest of the array (O(N-K)). The total time is O(K + N - K) = O(N).

Space

O(1). We only use a few variables for the window sum, count, and loop index, which requires constant extra space.

Trade-offs

Pros

Highly efficient with a linear time complexity, making it suitable for large inputs.
This is the optimal solution for this problem.

Cons

Slightly more complex to conceptualize than the brute-force method, though it's a very common and essential pattern.

Solutions

Solution

1class Solution { public int numOfSubarrays ( int [] arr , int k , int threshold ) { int s = 0 ; for ( int i = 0 ; i < k ; ++ i ) { s += arr [ i ]; } int ans = s / k >= threshold ? 1 : 0 ; for ( int i = k ; i < arr . length ; ++ i ) { s += arr [ i ] - arr [ i - k ]; ans += s / k >= threshold ? 1 : 0 ; } return ans ; } }

1class Solution { public: int numOfSubarrays ( vector < int >& arr , int k , int threshold ) { int s = accumulate ( arr . begin (), arr . begin () + k , 0 ); int ans = s >= k * threshold ; for ( int i = k ; i < arr . size (); ++ i ) { s += arr [ i ] - arr [ i - k ]; ans += s >= k * threshold ; } return ans ; } };

1class Solution : def numOfSubarrays ( self , arr : List [ int ], k : int , threshold : int ) -> int : s = sum ( arr [: k ]) ans = int ( s / k >= threshold ) for i in range ( k , len ( arr )): s += arr [ i ] s -= arr [ i - k ] ans += int ( s / k >= threshold ) return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem