Skip to main content
Talentd

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

MediumArraySliding Window13 min readAsked at: Amazon, Microsoft, Goldman Sachs +2
Practice this problem

Problem Statement

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.

 

Example 1:

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:

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.

 

Constraints:

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

Approach Overview

Problem Overview: You are given an integer array arr, a window size k, and a threshold. Count how many contiguous subarrays of length k have an average greater than or equal to the threshold. Since the subarray size is fixed, the task reduces to efficiently computing the sum of every window of length k and checking whether sum / k >= threshold.

Approach 1: Brute Force (Time: O(n * k), Space: O(1))

The straightforward method iterates over every possible subarray of length k. For each starting index, compute the sum of the next k elements using a loop, calculate the average, and compare it with the threshold. If the condition holds, increment the result counter. This approach uses no extra memory beyond a few variables, but repeatedly recalculates sums for overlapping windows. When n is large, recomputing each window from scratch becomes inefficient because each element is processed up to k times.

Approach 2: Sliding Window (Time: O(n), Space: O(1))

The optimal approach uses a Sliding Window over the Array. Instead of recomputing sums for each subarray, maintain the sum of the current window of size k. First compute the sum of the initial k elements. Then move the window one step to the right by subtracting the element leaving the window and adding the new element entering the window. Each shift updates the sum in constant time. Check whether windowSum >= k * threshold instead of computing division; this avoids floating-point operations and simplifies comparison.

Because each element enters and leaves the window exactly once, the total work is linear in the size of the array. The algorithm uses only a few variables to track the running sum and the result count, so the extra space remains constant. This technique appears frequently in problems where a fixed-size window moves across an array.

Recommended for interviews: The sliding window solution is the expected answer. Interviewers want to see that you recognize repeated work in overlapping subarrays and replace it with a rolling sum update. Mentioning the brute force approach first demonstrates understanding of the problem, but switching to the sliding window optimization shows algorithmic maturity and familiarity with common patterns like Sliding Window on arrays.

Approach 1: Sliding Window Approach

This approach utilizes the sliding window technique to calculate the sum of each sub-array of size k efficiently.

By maintaining a running sum of the current sub-array of size k and updating the sum as the window slides forward, we can avoid recalculating the sum from scratch each time, reducing the time complexity substantially.

The Python solution initializes the current sum with the sum of the first k elements. It uses a loop to subtract the element going out of the current sub-array and add the new element entering the sub-array window. If the resultant sum is greater than or equal to the target sum (k * threshold), the count is incremented.

Code

PythonC++JavaCC#JavaScript

Python

C++

Java

C

C#

JavaScript

Complexity

Time Complexity: O(n) - where n is the length of the array, as the algorithm processes each element once.

Space Complexity: O(1) - no extra space proportional to input size is used.

Try this approach in the editor →

Approach 2: Brute Force Approach

This approach employs a simple brute force strategy, computing the sum of each sub-array of length k individually and comparing it against the needed threshold multiplied by k.

This approach serves as a baseline for understanding the problem's requirements, though it is not optimal for large input sizes.

The Python brute force solution iterates over all possible k-length sub-arrays, computes their sum individually using the built-in sum function, and increments the count for those that meet or exceed the threshold times k.

Code

PythonC++JavaCC#JavaScript

Python

C++

Java

C

C#

JavaScript

Complexity

Time Complexity: O(nk) - the sum for each sub-array is recomputed in each iteration.

Space Complexity: O(1) - no additional storage other than basic variables is utilized.

Try this approach in the editor →

Approach 3: Sliding Window

We can multiply threshold by k, so that we can directly compare the sum within the window with threshold.

We maintain a sliding window of length k, and for each window, we calculate the sum s. If s is greater than or equal to threshold, we increment the answer.

The time complexity is O(n), where n is the length of the array arr. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sliding Window Approach

Time Complexity: O(n) - where n is the length of the array, as the algorithm processes each element once.

Space Complexity: O(1) - no extra space proportional to input size is used.

Brute Force Approach

Time Complexity: O(nk) - the sum for each sub-array is recomputed in each iteration.

Space Complexity: O(1) - no additional storage other than basic variables is utilized.

Sliding Window—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute ForceO(n * k)O(1)Good for understanding the problem or when constraints are very small
Sliding WindowO(n)O(1)Optimal approach for fixed-size subarray problems and large inputs

Video Solution

Number of Subarrays of size K and Average Greater than or Equal to Threshold - Leetcode 1343 Python • NeetCodeIO • 16,837 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold easy or hard?
The problem is typically rated Medium because the brute force solution is simple but inefficient. Recognizing that overlapping subarrays share most of their elements and applying a sliding window optimization is the key step interviewers expect.
Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold Python/Java solution
Most implementations follow the same sliding window logic regardless of language. Compute the initial window sum, slide the window by updating the sum with arr[i] and arr[i-k], and count windows where sum >= k * threshold. This pattern translates directly to Python, Java, C++, C, C#, and JavaScript.
How to solve Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold in O(n)?
Compute the sum of the first k elements, then slide the window across the array. For each step, subtract the element leaving the window and add the new element entering it. Instead of calculating the average each time, compare windowSum with k * threshold to check if the condition holds.
What is the best approach for Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold?
The sliding window approach is the most efficient solution. Maintain the sum of a fixed-size window of length k and update it as the window moves across the array by subtracting the outgoing element and adding the incoming one. Each update takes constant time, resulting in O(n) time complexity and O(1) extra space.
Is Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold asked at Google/Amazon/Meta?
Array and sliding window problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. The question tests recognition of fixed-size window optimization and the ability to reduce repeated computations from O(n*k) to O(n).
What data structure is used in Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold?
The problem primarily uses an array with the sliding window technique. No complex data structures are required—just a running sum variable to maintain the current window's total while iterating through the array.
What is the time complexity of Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold?
The optimal sliding window solution runs in O(n) time because each array element is processed at most twice—once when entering the window and once when leaving it. The brute force approach requires O(n * k) time since it recomputes the sum of every subarray of size k from scratch.

Ready to solve this problem?

Practice Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold with our built-in code editor and test cases.

Practice on FleetCode
Previous

Apply Operations to Make All Array Elements Equal to Zero

Next

Count Subarrays With Median K