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

  1. Initialize a window sum with the sum of the first k elements.
  2. If the window sum is at least k * threshold, increment the answer.
  3. Slide the window by removing the leftmost element and adding the next element to the right.
  4. Repeat steps 2-3 for all possible windows.
  5. Return the answer.

Code

 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
}
 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;
    }
}
 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
    }
}
 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
 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
    }
}
 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.