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

Given an integer array arr and integers k and threshold, return the number of subarrays of length k whose average is at least threshold. This is LeetCode 1343.

Example 1
Input: arr = [2, 2, 2, 2, 5, 5, 5, 8], k = 3, threshold = 4
Output: 3
Explanation: [2, 5, 5], [5, 5, 5] and [5, 5, 8] have averages 4, 5 and 6.
Example 2
Input: arr = [11, 13, 17, 23, 29, 31, 7, 5, 2, 3], k = 3, threshold = 5
Output: 6

How to Think About It

Step 1: Avoid division

"Average at least threshold" means sum / k >= threshold. Multiply both sides by k: sum >= k × threshold. Comparing whole numbers avoids floating point.

Step 2: A window of fixed size

Keep the sum of the last k elements. Each step adds arr[i] and, once the window is full, subtracts arr[i - k].

Step 3: Count the windows that qualify

From i = k - 1 on, every i ends a full window. If its sum is at least k × threshold, add one to the count.

Walkthrough

arr = [2, 2, 2, 2, 5, 5, 5, 8], k = 3, threshold = 4. A window qualifies when its sum is at least 12.

WindowSumAt least 12?Count
[2, 2, 2]6no0
[2, 2, 2]6no0
[2, 2, 5]9no0
[2, 5, 5]12yes1
[5, 5, 5]15yes2
[5, 5, 8]18yes3

Java Solution

k × threshold is at most 105 × 104 = 109, which still fits in an int.

Java
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, NumberOfSubArraysOfSizeKAndAvgGreaterThanOrEqualToThreshold.java, is on GitHub.

Complexity

  • Time: O(n).
  • Space: O(1).

To find the single best window instead of counting, see Maximum Average Subarray I.