Fixed-Size Windows

The redundant work brute force does

A window is a contiguous slice of an array or string. A fixed-size window problem asks something about every window of size k as it slides across the input — most classically, "what's the maximum sum over any k consecutive elements?" The brute force sums each window fresh:

Each sum costs O(k), and there are n − k + 1 windows: O(n·k) total. For k anywhere near n, that's the O(n²) from Module 4's opening example wearing a new costume — and the redundancy is visible in the trace above: windows 1 and 2 share elements 1 and 5. Recomputing their sum from scratch throws that shared work away.

Slide instead of recompute

A window moving one step right doesn't change much: it drops its leftmost element and picks up one new element on the right. So don't recompute the sum — update it. It's the same move as dragging a crop box across an image one pixel at a time: you don't re-crop from scratch on every nudge, you discard the thin strip that fell off the left edge and paint in the thin strip that entered on the right.

new_sum = old_sum − (element leaving) + (element entering)

Each slide is O(1) — one subtraction, one addition — regardless of k. Total cost: O(k) to prime the first window, then O(1) per slide across n − k remaining positions: O(n), independent of k. This is the converging-pointers trick's sibling: instead of two pointers eliminating candidates, here one pointer pair (left, right) drags a window, and the saving comes from incremental maintenance rather than batch elimination. Different mechanism, same economic shape: find what's shared between adjacent subproblems and stop recomputing it.

Step through the exact example above — the window never re-sums, it only trades one element for another:

The template

def max_window_sum(nums: list[int], k: int) -> int:
    window_sum = sum(nums[:k])          # prime: O(k), once
    best = window_sum
    for right in range(k, len(nums)):
        left = right - k                # the element leaving
        window_sum += nums[right] - nums[left]   # slide: O(1)
        best = max(best, window_sum)
    return best

Notice what makes this legal: sum is incrementally maintainable — knowing the old sum and exactly which element enters/leaves is enough to compute the new sum, with no need to re-examine the untouched middle. That property is doing all the work, and it's worth stating as a question you ask before reaching for this template: "if I know the answer for window i, and I know what's entering and leaving, can I get the answer for window i+1 without rescanning?" Sum, count, and running XOR all qualify trivially. Max and min do not — losing the leaving element might have been the max, and nothing short of a rescan (or a smarter structure) tells you the new max. That's exactly why Sliding Window Maximum (Module 9) needed the monotonic deque instead of this template: max isn't incrementally maintainable with O(1) bookkeeping, so the technique reached for a structure that tracks candidates, not just a running scalar.

Generalizing beyond sums

The same slide idea works for any aggregate with an efficient "remove one, add one" update:

• Count matching a predicate (e.g., vowels in the window): ±1 per slide, same as sum.
• Frequency map (Hash Tables' Count verb, windowed): decrement the leaving character's count, increment the entering one — O(1) if you track "how many distinct counts are currently correct" alongside the map, as the Permutation in String problem will show.
• XOR / product (with care for zero): symmetric to sum, with one trap sum doesn't have — sum's inverse operation is subtraction, always safe, but product's inverse is division, and dividing by a leaving element of 0 is undefined. A running product needs a special case (or a count of how many zeros are currently in the window) that a running sum never does.