042. Count Fixed Windows Above Threshold

Why this mechanism works

The sum update is identical to maximum fixed-window sum, but the commit operation is a qualification count rather than a maximum. Only evaluate complete size-k windows; a shorter prefix may satisfy the numeric threshold but is not a legal candidate.

State and boundaries

total describes the current complete window. count is the number of visited complete windows with total>=threshold.

Protocol

1. Handle invalid k.
2. Evaluate the first complete window.
3. Replace one departing value with each incoming value.
4. Add one when the new complete sum qualifies.
5. Return count.

Visualization

size 3 sums: 8, 7, 9, 6
threshold 8: Y, N, Y, N
count: 2

Python implementation

def count_windows(nums, k, threshold):
    if k < 1 or k > len(nums):
        return 0
    total = sum(nums[:k])
    count = int(total >= threshold)
    for right in range(k, len(nums)):
        total += nums[right] - nums[right - k]
        count += int(total >= threshold)
    return count

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 count_windows: if k < 1 or k > len(nums):
nums=[2, 1, 5, 1, 3, 2]; k=3; threshold=8

L4 count_windows: total = sum(nums[:k])
nums=[2, 1, 5, 1, 3, 2]; k=3; threshold=8; total=8

L5 count_windows: count = int(total >= threshold)
nums=[2, 1, 5, 1, 3, 2]; k=3; threshold=8; total=8; count=1

L6 count_windows: for right in range(k, len(nums)):
nums=[2, 1, 5, 1, 3, 2]; k=3; threshold=8; total=8; count=1; right=3

L7 count_windows: total += nums[right] - nums[right - k]
nums=[2, 1, 5, 1, 3, 2]; k=3; threshold=8; total=7; count=1; right=3

L6 count_windows: for right in range(k, len(nums)):
nums=[2, 1, 5, 1, 3, 2]; k=3; threshold=8; total=7; count=1; right=4

L7 count_windows: total += nums[right] - nums[right - k]
nums=[2, 1, 5, 1, 3, 2]; k=3; threshold=8; total=9; count=1; right=4

L8 count_windows: count += int(total >= threshold)
nums=[2, 1, 5, 1, 3, 2]; k=3; threshold=8; total=9; count=2; right=4

L6 count_windows: for right in range(k, len(nums)):
nums=[2, 1, 5, 1, 3, 2]; k=3; threshold=8; total=9; count=2; right=5

L7 count_windows: total += nums[right] - nums[right - k]
nums=[2, 1, 5, 1, 3, 2]; k=3; threshold=8; total=6; count=2; right=5

L2 count_windows: if k < 1 or k > len(nums):
nums=[2, 2]; k=1; threshold=2

L4 count_windows: total = sum(nums[:k])
nums=[2, 2]; k=1; threshold=2; total=2

L5 count_windows: count = int(total >= threshold)
nums=[2, 2]; k=1; threshold=2; total=2; count=1

L6 count_windows: for right in range(k, len(nums)):
nums=[2, 2]; k=1; threshold=2; total=2; count=1; right=1

L8 count_windows: count += int(total >= threshold)
nums=[2, 2]; k=1; threshold=2; total=2; count=2; right=1

Why the solution is correct

The replacement recurrence enumerates exactly the size-k windows. Each contributes either one or zero according to the required predicate, so the accumulated count neither misses qualifying windows nor includes partial ones.

Time and space

O(n) time; O(k) temporary slice space and O(1) persistent state.

Common mistakes

Counting before a full window exists introduces extra candidates. Using > instead of >= loses threshold-equal windows.

Reasoning card

Transfer exercise

Count windows whose average reaches a threshold using a sum comparison, and explain when multiplication avoids floating-point error.