Number of Sub-arrays of Size K and Average Greater Than or Equal to Threshold Problem#
Problem#
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
.
Examples#
Example 1:
1
2
3
4
5
|
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:
1
2
3
4
5
|
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.
|
Solution#
Method 1 – Sliding Window Sum#
Intuition#
To efficiently count subarrays of size k
with average at least threshold
, we can use a sliding window of size k
and keep track of the sum. If the sum of the window is at least k * threshold
, the average is sufficient.
Approach#
- Initialize a window sum with the sum of the first
k
elements.
- If the window sum is at least
k * threshold
, increment the answer.
- Slide the window by removing the leftmost element and adding the next element to the right.
- Repeat steps 2-3 for all possible windows.
- Return the answer.
Code#
C++#
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution {
public:
int numOfSubarrays(vector<int>& arr, int k, int threshold) {
int ans = 0, sum = 0;
for (int i = 0; i < arr.size(); ++i) {
sum += arr[i];
if (i >= k) sum -= arr[i - k];
if (i >= k - 1 && sum >= k * threshold) ans++;
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
func numOfSubarrays(arr []int, k int, threshold int) int {
ans, sum := 0, 0
for i := 0; i < len(arr); i++ {
sum += arr[i]
if i >= k {
sum -= arr[i-k]
}
if i >= k-1 && sum >= k*threshold {
ans++
}
}
return ans
}
|
Java#
1
2
3
4
5
6
7
8
9
10
11
|
class Solution {
public int numOfSubarrays(int[] arr, int k, int threshold) {
int ans = 0, sum = 0;
for (int i = 0; i < arr.length; i++) {
sum += arr[i];
if (i >= k) sum -= arr[i - k];
if (i >= k - 1 && sum >= k * threshold) ans++;
}
return ans;
}
}
|
Kotlin#
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution {
fun numOfSubarrays(arr: IntArray, k: Int, threshold: Int): Int {
var ans = 0
var sum = 0
for (i in arr.indices) {
sum += arr[i]
if (i >= k) sum -= arr[i - k]
if (i >= k - 1 && sum >= k * threshold) ans++
}
return ans
}
}
|
Python#
1
2
3
4
5
6
7
8
9
10
11
|
class Solution:
def numOfSubarrays(self, arr: list[int], k: int, threshold: int) -> int:
ans = 0
s = sum(arr[:k])
if s >= k * threshold:
ans += 1
for i in range(k, len(arr)):
s += arr[i] - arr[i - k]
if s >= k * threshold:
ans += 1
return ans
|
Rust#
1
2
3
4
5
6
7
8
9
10
11
12
|
impl Solution {
pub fn num_of_subarrays(arr: Vec<i32>, k: i32, threshold: i32) -> i32 {
let (mut ans, mut sum) = (0, 0);
let k = k as usize;
for i in 0..arr.len() {
sum += arr[i];
if i >= k { sum -= arr[i - k]; }
if i + 1 >= k && sum >= (k as i32) * threshold { ans += 1; }
}
ans
}
}
|
TypeScript#
1
2
3
4
5
6
7
8
9
10
11
|
class Solution {
numOfSubarrays(arr: number[], k: number, threshold: number): number {
let ans = 0, sum = 0;
for (let i = 0; i < arr.length; i++) {
sum += arr[i];
if (i >= k) sum -= arr[i - k];
if (i >= k - 1 && sum >= k * threshold) ans++;
}
return ans;
}
}
|
Complexity#
- ⏰ Time complexity:
O(n)
, where n
is the length of the array, since each element is processed once.
- 🧺 Space complexity:
O(1)
, as only a few variables are used for tracking the window sum and answer.