Introduction

The Number of Sub-arrays of Size K and Average ≥ Threshold problem asks us to count how many contiguous subarrays of exactly k elements have an average greater than or equal to a given threshold.

Because every subarray has the same size, a fixed-size Sliding Window can efficiently solve the problem.

Problem Statement

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

Example

Input:arr = [2, 2, 2, 2, 5, 5, 5, 8]
k = 3
threshold = 4

Output:
3

Explanation:
[2, 2, 2]
Average = 2
[2, 2, 2]
Average = 2
[2, 2, 5]
Average = 3
[2, 5, 5]
Average = 4
[5, 5, 5]
Average = 5
[5, 5, 8]
Average = 6
There are 3 subarrays with average >= 4.

Constraints

  • 1 ≤ arr.length ≤ 10⁵
  • 1 ≤ k ≤ arr.length
  • 0 ≤ arr[i] ≤ 10⁴
  • 0 ≤ threshold ≤ 10⁴

Premium Video

This video is available to Premium members or users who have purchased the course.

Sign in to Unlock

Approach 1: Brute Force

Explanation

We can examine every possible subarray of size k.

For every window:

  1. Calculate the sum of its k elements.
  2. Calculate the average.
  3. Check whether the average is at least threshold.
  4. If yes, increase the count.

This requires recalculating the sum for every window.

Steps

  1. Start from the first index.
  2. Calculate the sum of the next k elements.
  3. Calculate the average.
  4. Compare the average with threshold.
  5. Increase the count if the condition is satisfied.
  6. Move to the next starting position.
  7. Repeat until all windows are checked.

Dry Run

arr = [2, 2, 2, 2, 5, 5, 5, 8]
k = 3
threshold = 4

Window 1:
[2, 2, 2]
Sum = 6
Average = 6 / 3 = 2
Count = 0

Window 2:
[2, 2, 2]
Sum = 6
Average = 2
Count = 0

Window 3:
[2, 2, 5]
Sum = 9
Average = 3
Count = 0

Window 4:
[2, 5, 5]
Sum = 12
Average = 4
Count = 1

Window 5:
[5, 5, 5]
Sum = 15
Average = 5
Count = 2

Window 6:
[5, 5, 8]
Sum = 18
Average = 6
Count = 3

Final Count = 3

Brute Force Code

Complexity Analysis

Time Complexity: O(n × k)

Space Complexity: O(1)

Approach 2: Optimized Solution Using Sliding Window

Explanation

We can avoid recalculating the entire sum for every window.

First, calculate the sum of the first k elements.

When the window moves:

  • Add the new element entering the window.
  • Remove the old element leaving the window.

Since:

Average ≥ Threshold

is equivalent to:

Sum ≥ k × Threshold

we can compare the window sum directly without calculating the average.

This makes the solution more efficient.

Steps

  1. Calculate the sum of the first k elements.
  2. Check whether the sum is at least k × threshold.
  3. Move the window one position.
  4. Add the incoming element.
  5. Remove the outgoing element.
  6. Check the new window sum.
  7. Continue until all windows are processed.

Dry Run

arr = [2, 2, 2, 2, 5, 5, 5, 8]k = 3
threshold = 4

Required Sum:
k × threshold
= 3 × 4
= 12

Initial Window:
[2, 2, 2]
Sum = 6
6 < 12
Count = 0

Slide:
Add 2
Remove 2

Window:
[2, 2, 2]
Sum = 6
6 < 12
Count = 0

Slide:
Add 5
Remove 2

Window:
[2, 2, 5]
Sum = 9
9 < 12
Count = 0

Slide:
Add 5
Remove 2

Window:
[2, 5, 5]
Sum = 12
12 >= 12
Count = 1

Slide:
Add 5
Remove 2

Window:
[5, 5, 5]
Sum = 15
15 >= 12
Count = 2

Slide:
Add 8
Remove 5

Window:
[5, 5, 8]
Sum = 18
18 >= 12
Count = 3

Final Count = 3

Optimized Code

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Edge Cases

  • k = 1: Each element forms its own subarray.
  • k = n: Only one subarray exists.
  • No subarray satisfies the threshold.
  • Every subarray satisfies the threshold.
  • The average is exactly equal to the threshold.

Why This Problem is Important

This problem teaches how a fixed-size sliding window can efficiently process consecutive elements without recalculating the entire window.

It also demonstrates how an average comparison can be converted into a simpler sum comparison.

Real-World Applications

This technique can be used for:

  • Monitoring average performance over fixed periods.
  • Analyzing sensor readings.
  • Processing financial or sales data.
  • Detecting periods that meet a minimum average.
  • Evaluating rolling performance metrics.

Common Mistakes

  • Recalculating the entire window sum.
  • Forgetting to remove the outgoing element.
  • Using threshold instead of k × threshold when comparing sums.
  • Using an incorrect window size.
  • Forgetting to check the initial window.

Interview Tips

  • Recognize that the window size is fixed.
  • Convert average ≥ threshold into sum ≥ k × threshold.
  • Maintain the window sum while sliding.
  • Add the incoming element and remove the outgoing element.
  • Initialize and check the first window before sliding.

Related Questions

  • Maximum Average Subarray I
  • Maximum Consecutive Ones
  • Maximum Consecutive Ones III
  • Minimum Size Subarray Sum
  • Subarray Sum Equals K

Final Takeaway

The Brute Force approach recalculates the sum for every window and takes O(n × k) time.

The Sliding Window approach maintains the current window sum and takes only O(n) time with O(1) extra space.

Key Idea: Since every window contains exactly k elements, compare its sum with k × threshold instead of calculating the average each time.