NeetCode #223LC-1343MediumSliding Window
← Back to All Problems#223 · #1343 · Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold(大小为 K 且平均值大于等于阈值的子数组数目)
📌 Problem Statement & Constraints
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. Constraints: 1 <= arr.length <= 10^5, 1 <= arr[i] <= 10^4, 1 <= k <= arr.length, 0 <= threshold <= 10^4.💡 Core Algorithmic Approaches
- Maintaining the window sum is cheaper than recomputing it, and the average condition is equivalent to
sum >= k * threshold. - Compute the sum of the first window, then slide by adding the entering element and removing the leaving one.
- Count windows satisfying the condition.
- Comparing sums rather than averages avoids floating-point division entirely.
💻 Benchmark Python3 Implementation
class Solution:
def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
total = sum(arr[:k])
res = 1 if total >= k * threshold else 0
for i in range(k, len(arr)):
total += arr[i] - arr[i - k]
if total >= k * threshold:
res += 1
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one pass after an O(k) initial sum.
💾 Space Complexity
O(1): a single accumulator.
⚠️ Interview Pitfalls & Follow-ups
- Dividing by
kand comparing tothreshold: this introduces floating-point arithmetic; comparingtotal >= k * thresholdis exact. - Recomputing the sum for each window: O(n * k).
- Forgetting the initial window: it must be counted before the slide loop.
- Using
>instead of>=: the condition is *greater than or equal to*.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.