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

Medium
243.

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 coding problem on arrays and sliding window, asked in Amazon and Google interviews.

Given an array of integers arr and two integers k and threshold, return the number of sub-arrays of size k whose average is greater than or equal to threshold.

Example 1

Input
arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4
Output
3
Explanation
The qualifying windows are [2,5,5], [5,5,5] and [5,5,8].

Example 2

Input
arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5
Output
6

Example 3

Input
arr = [1,1,1], k = 3, threshold = 2
Output
0

Constraints

  • 1 <= arr.length <= 40
  • 1 <= arr[i] <= 100
  • 1 <= k <= arr.length
  • 0 <= threshold <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @param {number} k
 * @param {number} threshold
 * @return {number}
 */
var numOfSubarrays = function(arr, k, threshold) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 solution: step-by-step approach, complexity and code in Python, Java, C++ and…

Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold is a medium coding problem on arrays and sliding window, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Sliding Window
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given an array of integers arr and two integers k and threshold, return the number of sub-arrays of size k whose average is greater than or equal to threshold.

Example 1

Input: arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4
Output: 3
Explanation: The qualifying windows are [2,5,5], [5,5,5] and [5,5,8].

Example 2

Input: arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5
Output: 6

Example 3

Input: arr = [1,1,1], k = 3, threshold = 2
Output: 0

Constraints

  • 1 <= arr.length <= 40
  • 1 <= arr[i] <= 100
  • 1 <= k <= arr.length
  • 0 <= threshold <= 100

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

  1. Hint 1

    Avoid division entirely: sum / k >= threshold is the same as sum >= k * threshold for positive k.

  2. Hint 2

    Maintain the window sum and slide it, adding the entering element and subtracting the leaving one.

  3. Hint 3

    Count a window the moment its sum clears the bar.

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

Avoid division: for positive k, sum / k >= threshold is equivalent to sum >= k · threshold. Slide a fixed window and compare its sum against that bar.

Approach

  1. Compute need = k * threshold and the sum of the first window.
  2. For each new position, add the entering element and subtract the leaving one.
  3. Count every window whose sum is at least need.

Why it works

The windows overlap by k - 1 elements, so each sum is the previous sum adjusted by two values. Comparing integers instead of averages sidesteps rounding entirely.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Count the first window before the loop starts.

Reference solution

Python

def numOfSubarrays(arr, k: int, threshold: int) -> int:
    need = k * threshold
    total = sum(arr[:k])
    count = 1 if total >= need else 0
    for i in range(k, len(arr)):
        total += arr[i] - arr[i - k]
        if total >= need:
            count += 1
    return count

Java

public static 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;
}

C++

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

JavaScript

var numOfSubarrays = function(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;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sliding Window Technique