Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold
Given an integer array arrkthresholdkthreshold
Example 1
Output: 3
Explanation: [2, 5, 5], [5, 5, 5] and [5, 5, 8] have averages 4, 5 and 6.
Example 2
Output: 6
How to Think About It
Step 1: Avoid division
"Average at least thresholdsum / k >= thresholdksum >= k × threshold
Step 2: A window of fixed size
Keep the sum of the last karr[i]arr[i - k]
Step 3: Count the windows that qualify
From i = k - 1ik × threshold
Walkthrough
arr = [2, 2, 2, 2, 5, 5, 5, 8]k = 3threshold = 4
| Window | Sum | At least 12? | Count |
|---|---|---|---|
| [2, 2, 2] | 6 | no | 0 |
| [2, 2, 2] | 6 | no | 0 |
| [2, 2, 5] | 9 | no | 0 |
| [2, 5, 5] | 12 | yes | 1 |
| [5, 5, 5] | 15 | yes | 2 |
| [5, 5, 8] | 18 | yes | 3 |
Java Solution
k × thresholdint
public class NumberOfSubArraysOfSizeKAndAvgGreaterThanOrEqualToThreshold {
public static int numOfSubarrays(int[] arr, int k, int threshold) {
int need = k * threshold; // average >= threshold <=> sum >= k * threshold
int sum = 0;
int count = 0;
for (int i = 0; i < arr.length; i++) {
sum += arr[i];
if (i >= k) {
sum -= arr[i - k]; // keep exactly k elements
}
if (i >= k - 1 && sum >= need) {
count++;
}
}
return count;
}
public static void main(String[] args) {
System.out.println(numOfSubarrays(new int[] {2, 2, 2, 2, 5, 5, 5, 8}, 3, 4)); // 3
int[] b = {11, 13, 17, 23, 29, 31, 7, 5, 2, 3};
System.out.println(numOfSubarrays(b, 3, 5)); // 6
}
}
The original implementation,
Complexity
- Time: O(n).
- Space: O(1).
To find the single best window instead of counting, see