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.

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.

Description Hints 2 Solution Video 7:33

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

Q: 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.

Q: 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.

Q: 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.

Q: 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).

Medium74.3% acceptance5 companies

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 <= 10⁵
1 <= arr[i] <= 10⁴
1 <= k <= arr.length
0 <= threshold <= 10⁴

Asked at 5 companies

LinkedIn Goldman Sachs

Google Amazon Microsoft

Topics

Array Sliding Window

Hints open one at a time

Hint 1

Start with a window of size K and test its average against the threshold.

Hint 2

Keep moving the window by one element maintaining its size k until you cover the whole array. Count the number of windows that have an average greater than or equal to the threshold.

7:33

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution