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

Medium Arrays & Hashing Sliding Window · Fixed Original on LeetCode

Reported atRazorpay

Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold is a medium arrays & hashing problem solved with the sliding window · fixed pattern. The best approach, optimal (fixed-size sliding window), runs in O(n) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (sum every window) up.

Problem

You are given an integer array arr and two integers k and threshold.

Count the contiguous subarrays of length exactly k whose average value is greater than or equal to threshold, and return that count.

Examples

Example 1

Input
arr = [3, 7, 2, 6, 1, 8], k = 2, threshold = 4
Output
4
Why
The windows of size 2 have sums 10, 9, 8, 7 and 9; all except [6, 1] (sum 7, average 3.5) reach an average of 4.

Example 2

Input
arr = [5, 5, 5, 5], k = 4, threshold = 5
Output
1
Why
There is only one window of size 4, and its average is exactly 5.

Example 3

Input
arr = [1, 2, 1], k = 1, threshold = 3
Output
0
Why
No single element is 3 or more.

Constraints

  • 1 <= arr.length <= 10^5
  • 1 <= arr[i] <= 10^4
  • 1 <= k <= arr.length
  • 0 <= threshold <= 10^4

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (sum every window)O(n · k)O(1)
Optimal (fixed-size sliding window)O(n)O(1)

1Brute force (sum every window)

TimeO(n · k)There are n - k + 1 windows and each one is summed from scratch in O(k).
SpaceO(1)Only a running sum and a counter.

For each starting index, add up the k elements of that window and check whether the sum reaches k * threshold. Comparing the sum with k * threshold avoids floating point.

  1. need = k * threshold.
  2. For each start i from 0 to n - k, sum arr[i..i+k-1].
  3. If sum >= need, count it.
class Solution {
    public int numOfSubarrays(int[] arr, int k, int threshold) {
        int need = k * threshold;
        int count = 0;
        for (int i = 0; i + k <= arr.length; i++) {
            int sum = 0;
            for (int j = i; j < i + k; j++) sum += arr[j];
            if (sum >= need) count++;
        }
        return count;
    }
}

2Optimal (fixed-size sliding window)

TimeO(n)Every element enters and leaves the window once.
SpaceO(1)Only the running sum and a counter.

Keep the sum of the current window of size k. Moving the window right by one adds the new element and subtracts the one that falls off the left, so each window's sum costs O(1).

  1. need = k * threshold; sum = arr[0] + … + arr[k - 1]; count = (sum >= need) ? 1 : 0.
  2. For i from k to n - 1: sum += arr[i] - arr[i - k].
  3. If sum >= need, count++.
  4. Return count.
class Solution {
    public int numOfSubarrays(int[] arr, int k, int threshold) {
        int need = k * threshold;
        int sum = 0;
        for (int i = 0; i < k; i++) sum += arr[i];
        int count = sum >= need ? 1 : 0;
        for (int i = k; i < arr.length; i++) {
            sum += arr[i] - arr[i - k];
            if (sum >= need) count++;
        }
        return count;
    }
}

Edge cases to test

  • k equal to the array length: only one window
  • k = 1: just count the elements that are at least the threshold
  • threshold = 0: every window qualifies
  • An average exactly equal to the threshold counts

Hints

Hint 1

Comparing averages means dividing. Can you compare the window sum with k * threshold instead?

Hint 2

Neighbouring windows share k - 1 elements. When the window slides one step, what changes in its sum?

FAQ

What is the best time complexity for Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold?

Optimal (fixed-size sliding window) runs in O(n) time and O(1) extra space. Every element enters and leaves the window once.

Which pattern does Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold use?

It is a arrays & hashing problem that uses the sliding window · fixed pattern. Other problems with the same pattern: Maximum Average Subarray I, K Radius Subarray Averages, Maximum Number of Vowels in a Substring of Given Length.

Is there a brute force solution for Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold?

Yes. Brute force (sum every window) takes O(n · k) time and O(1) space. For each starting index, add up the k elements of that window and check whether the sum reaches k threshold.

Which edge cases should I test for Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold?

k equal to the array length: only one window; k = 1: just count the elements that are at least the threshold; threshold = 0: every window qualifies; An average exactly equal to the threshold counts.