Sliding window

The problem it solves

A whole family of problems asks about every contiguous run of an array: the biggest sum of any k consecutive elements, the moving average of a sensor feed, the window of traffic that exceeded a rate limit, whether any k-wide stretch of a string is an anagram of a pattern. The obvious code computes each window from scratch — n windows, k work each, O(n·k) — and for a day of per-second readings with a one-hour window that is 86,400 × 3,600 ≈ 300 million operations to answer a question the data can answer in one pass.

The sliding window technique is the one-pass answer, and it rests on a single observation so small it is easy to under-rate: adjacent windows overlap in all but two elements. Window a[i..i+k−1] and window a[i+1..i+k] share k−1 members. Whatever summary you maintain — a sum here — does not need recomputing; it needs one element added and one removed. O(n) total, O(1) space, and the pattern generalises far beyond sums: counts, frequency tables, monotonic deques for maxima. It is less an algorithm than a shape of algorithm, and interviews lean on it because recognising the shape is the skill.

The intuition — and where it breaks down

Picture a physical stencil k slots wide laid over the bars, and slide it one slot right. Almost everything under the stencil is what was there before — one bar entered on the right, one fell out on the left. If you are tracking the total height, you would never re-measure the middle; you add the newcomer and subtract the leaver. The visualization draws exactly this: the marker band glides, and per slide exactly two bars flash — enter and leave. That two-bar flash is the technique.

Two places the picture misleads. First, it assumes the thing you track can be updated incrementally in both directions — a sum can (subtraction undoes addition), but a maximum cannot: when the tallest bar leaves the stencil, knowing the old max tells you nothing about the new one, and you need heavier machinery (a monotonic deque) to stay O(n). Second, the picture is about fixed-width stencils. The equally famous variable-width cousin — “longest subarray with sum ≤ S” — grows the right edge and shrinks the left edge on a condition, and only works when the predicate is monotone: shrinking a violating window must move it toward validity. Both breakdowns are favourite interview follow-ups precisely because the basic picture hides them.

Loading…

A walkthrough you can check

Find the max-sum window of width 3 in [4, 2, 9, 1, 5, 3].

1. Sum the first window honestly: 4 + 2 + 9 = 15. This is the only from-scratch sum ever computed; best so far 15, starting at 0.
2. Slide: 1 enters, 4 leaves. New sum 15 + 1 − 4 = 12. Two operations. Best stays 15.
3. Slide: 5 enters, 2 leaves. 12 + 5 − 2 = 15. Ties do not displace the incumbent (strict >), so best remains the first 15 — a detail that matters the moment the answer is “return the earliest such window”.
4. Slide: 3 enters, 9 leaves. 15 + 3 − 9 = 9. Best still 15.

Answer: window a[0..2], sum 15. Total arithmetic after the first window: three slides × two operations, versus brute force’s four windows × three additions. The gap is comic at n = 6 and decisive at n = 10⁶. The player’s mid-run prediction asks precisely the step-3 arithmetic — current sum, plus enterer, minus leaver — because being able to do that update reflexively is the whole game.

The invariant

The maintained sum always equals the true sum of the current window a[L..R]. It holds after the honest first computation, and every slide preserves it: the true sum changes by exactly (entering − leaving), and that is exactly what the code adds and subtracts. Nothing else in the window changed — that is what “contiguous, slide by one” guarantees — so nothing else needs touching.

The second, quieter invariant: best is the maximum over all windows examined so far, held by the earliest window achieving it. The strict comparison maintains the “earliest” clause. Together the two invariants make the final answer correct by construction: every window is examined (R sweeps left to right), each one’s sum is exact (first invariant), and the running maximum never misses or misorders (second).

When the window generalises — counts of each character, number of distinct values, a deque of candidate maxima — the proof obligation stays identical: whatever summary you keep must be exactly right after each slide. If you can state that invariant for your summary, the pattern applies; if you cannot, it does not.

Complexity, derived

The first window costs k operations. Each of the n − k slides costs exactly two (one add, one subtract) plus one comparison against best: O(1) per slide, with no hidden loops. Total O(k + (n−k)) = O(n) time, O(1) space — two indices, two accumulators. The unit suite pins this honestly: the trace’s comparison counter equals n − k, not a big-O hand-wave but an exact count.

Compare brute force: (n−k+1) windows × k additions = O(n·k), which for k = n/2 is quadratic. The speed-up factor is k itself — the wider the window, the more the overlap observation pays. For the variable-size variant, the analysis changes shape but not answer: L and R each move only rightward, at most n steps apiece, so total work is O(n) amortised even though a single arrival can trigger many departures. Saying the word “amortised” there, and knowing why per-step bounds fail but total bounds hold, is what separates a memorised pattern from an understood one.

What people get wrong

• Recomputing the window — writing the O(n·k) loop while calling it sliding window. The name refers to the update rule, not to the mere presence of a window.
• The leaving index: when right enters a window of width k, the leaver is right − k, not right − k + 1. Off-by-one here silently corrupts every subsequent sum — the invariant dies at the first slide and nothing crashes.
• Sliding a maximum like a sum: subtracting the departed max is meaningless. Max-in-window needs the monotonic deque; knowing why the naive update fails (maxima are not invertible) is the actual test.
• Forcing the fixed-size pattern onto variable-size problems — “longest subarray with at most two distinct values” needs the grow-right / shrink-left form, not a fixed k.
• Using it where the predicate is not monotone: “window sum divisible by 7” cannot drive a shrink decision — shrinking may fix or break divisibility unpredictably. Prefix sums with a hash map is the right tool there.
• Ties and “earliest”: using >= instead of > returns the last best window, which fails specs (and tests) that ask for the first.

Implementation notes

The fixed-size form should look exactly like the displayed code: one honest sum, then a single loop carrying sum += a[right] − a[right−k]. Resist the urge to maintain both L and R variables when right − k derives one from the other — fewer moving parts, fewer off-by-ones. Overflow deserves a thought in 32-bit languages: k large values can exceed int range mid-window even when the answer fits, so accumulate in 64 bits.

The variable-size template is worth memorising as a shape: for right in 0..n−1: add a[right]; while window invalid: remove a[left]; left++ — then harvest the answer either inside the loop (longest valid) or when validity is first reached (shortest valid). Its correctness rests on monotonicity: removal must never make a valid window invalid.

For window maxima, keep a deque of indices with strictly decreasing values: pop the back while the newcomer is ≥ it (they can never be the answer again), push the newcomer, pop the front when it leaves the window. Every index enters and leaves the deque once — O(n) total, and the front is always the current max. This trio — fixed-size accumulate, variable-size two-pointer, monotonic deque — covers essentially every sliding-window interview question in circulation.

The follow-up questions

How does the variable-size variant stay O(n) when one step can shrink many times? Amortisation: each element is added by R exactly once and removed by L at most once, so total pointer movement is ≤ 2n regardless of how it clusters. Per-step cost is unbounded; total cost is linear.

Why does max-in-window need a deque when sum does not? A sum is invertible — subtracting the leaver restores the summary exactly. A max destroys information: after the max leaves, the runner-up is unknown unless you kept candidates. The monotonic deque keeps precisely the candidates that could still matter, and nothing else.

When does sliding window not apply at all? When windows are not contiguous (subsequences), when the tracked property cannot be updated incrementally, or when the shrink predicate is not monotone. The give-away phrase “contiguous subarray” invites the pattern; “subsequence” forbids it.

Sliding window versus prefix sums? Both answer range-sum questions in O(1) per query after O(n) setup. Prefix sums answer arbitrary ranges and non-monotone predicates (with a hash map); sliding window wins when the ranges are a moving front and you also need O(1) space or an online algorithm — it never stores more than the summary.