⚡Flashcard Drill➔
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

  1. Maintaining the window sum is cheaper than recomputing it, and the average condition is equivalent to sum >= k * threshold.
  2. Compute the sum of the first window, then slide by adding the entering element and removing the leaving one.
  3. Count windows satisfying the condition.
  4. 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 k and comparing to threshold: this introduces floating-point arithmetic; comparing total >= k * threshold is 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.
🎯 Drill This Card Now➔

🧩 Related Sliding Window Problems