Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold
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^51 <= arr[i] <= 10^41 <= k <= arr.length0 <= 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.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
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.
| Approach | Time | Space |
|---|---|---|
| Brute force (sum every window) | O(n · k) | O(1) |
| Optimal (fixed-size sliding window) | O(n) | O(1) |
1Brute force (sum every window)
O(n · k)There are n - k + 1 windows and each one is summed from scratch in O(k).O(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.
- need = k * threshold.
- For each start i from 0 to n - k, sum arr[i..i+k-1].
- 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;
}
}class Solution:
def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
need = k * threshold
count = 0
for i in range(len(arr) - k + 1):
s = 0
for j in range(i, i + k):
s += arr[j]
if s >= need:
count += 1
return countclass Solution {
public:
int numOfSubarrays(vector<int>& arr, int k, int threshold) {
int need = k * threshold;
int count = 0;
for (int i = 0; i + k <= (int)arr.size(); i++) {
int sum = 0;
for (int j = i; j < i + k; j++) sum += arr[j];
if (sum >= need) count++;
}
return count;
}
};function numOfSubarrays(arr, k, threshold) {
const need = k * threshold;
let count = 0;
for (let i = 0; i + k <= arr.length; i++) {
let sum = 0;
for (let j = i; j < i + k; j++) sum += arr[j];
if (sum >= need) count++;
}
return count;
}2Optimal (fixed-size sliding window)
O(n)Every element enters and leaves the window once.O(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).
- need = k * threshold; sum = arr[0] + … + arr[k - 1]; count = (sum >= need) ? 1 : 0.
- For i from k to n - 1: sum += arr[i] - arr[i - k].
- If sum >= need, count++.
- 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;
}
}class Solution:
def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
need = k * threshold
s = sum(arr[:k])
count = 1 if s >= need else 0
for i in range(k, len(arr)):
s += arr[i] - arr[i - k]
if s >= need:
count += 1
return countclass Solution {
public:
int numOfSubarrays(vector<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 < (int)arr.size(); i++) {
sum += arr[i] - arr[i - k];
if (sum >= need) count++;
}
return count;
}
};function numOfSubarrays(arr, k, threshold) {
const need = k * threshold;
let sum = 0;
for (let i = 0; i < k; i++) sum += arr[i];
let count = sum >= need ? 1 : 0;
for (let 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.