Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold - 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.

A sub-array is a contiguous sequence of elements within an array. The average of a sub-array is the sum of all elements divided by the number of elements.

Note: The average should be calculated as a floating-point number, but the comparison with threshold should handle integer arithmetic to avoid precision issues.

Input & Output

Example 1 — Basic Case
$ Input: arr = [2,4,2,1,5], k = 3, threshold = 2
Output: 3
💡 Note: Sub-array [2,4,2] has average (2+4+2)/3 = 2.67 ≥ 2. Sub-array [4,2,1] has average (4+2+1)/3 = 2.33 ≥ 2. Sub-array [2,1,5] has average (2+1+5)/3 = 2.67 ≥ 2. All three sub-arrays qualify, so answer is 3.
Example 2 — All Valid
$ Input: arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5
Output: 6
💡 Note: Most sub-arrays of size 3 have averages well above 5, so multiple sub-arrays qualify.
Example 3 — None Valid
$ Input: arr = [1,1,1,1,1], k = 1, threshold = 2
Output: 0
💡 Note: All elements are 1, which is less than threshold 2, so no sub-arrays qualify.

Constraints

  • 1 ≤ arr.length ≤ 105
  • 1 ≤ arr[i] ≤ 104
  • 1 ≤ k ≤ arr.length
  • 0 ≤ threshold ≤ 104

Visualization

Tap to expand
Sub-arrays with Average >= Threshold INPUT arr = [2, 4, 2, 1, 5] 2 i=0 4 i=1 2 i=2 1 i=3 5 i=4 k = 3 threshold = 2 min sum = k * threshold = 6 Window of size 3 sliding window ALGORITHM STEPS 1 Initialize count=0, sum of first k 2 Slide Window Add right, remove left 3 Check Condition if sum >= k*threshold 4 Count Valid Increment count Window Calculations: [2,4,2]: sum=8 >= 6 OK [4,2,1]: sum=7 >= 6 OK [2,1,5]: sum=8 >= 6 OK All 3 windows are valid! FINAL RESULT Valid Sub-arrays Found: [2, 4, 2] avg = 8/3 = 2.67 >= 2 [4, 2, 1] avg = 7/3 = 2.33 >= 2 [2, 1, 5] avg = 8/3 = 2.67 >= 2 Output: 3 3 valid sub-arrays found Key Insight: Sliding Window Optimization: Instead of recalculating sum for each window (O(n*k)), slide the window by adding the new element and removing the old one. This achieves O(n) time complexity. Compare sum with k*threshold to avoid division: sum >= k*threshold equals avg >= threshold. TutorialsPoint - Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold | Sliding Window Approach
Asked in
Amazon 15 Google 12 Microsoft 8
25.0K Views
Medium Frequency
~15 min Avg. Time
890 Likes
Ln 1, Col 1
Smart Actions
💡 Explanation
AI Ready
💡 Suggestion Tab to accept Esc to dismiss
// Output will appear here after running code
Code Editor Closed
Click the red button to reopen