Sliding Window

Imagine watching a street through a bus window. As the bus rolls forward, one new shop slides into view and one old shop slides out - you never re-scan the whole street each second, you just account for the one that entered and the one that left. A sliding window keeps a running total the same lazy way.

Example: the sum of every 3 numbers in a row in [2, 1, 5, 1, 3]. Start with 2 + 1 + 5 = 8. To slide one step right, subtract the 2 that left and add the 1 that entered, giving 7. Slide again: subtract 1, add 3, giving 9. Each move is a single add and a single subtract instead of re-adding three numbers from scratch.

A window is the range [left, right] (inclusive) currently under consideration, plus a running summary of what's inside it.

The invariant you maintain: after processing each `right`, the window state exactly reflects the elements in `[left, right]`. Keep that true and the logic stays simple.

When the window size k is fixed (e.g. "maximum sum of any k consecutive elements"), slide by adding the incoming element and subtracting the one that falls off the back. No inner loop needed.

Expand right every step. When adding a[right] breaks the condition, advance left (removing elements) until the window is valid again. Record the best length whenever the window is valid. Classic use: 'longest substring without repeating characters', 'longest substring with at most k distinct'.

Expand right until the window first becomes valid (e.g. its sum ≥ target, or it contains all required characters). Then shrink left as far as possible while it stays valid, recording the minimum length at each step. Classic use: 'minimum size subarray sum', 'minimum window substring'.

Even though there's a nested while loop in the variable templates, left only ever moves forward and never resets. Across the whole run, left advances at most n times total and right advances n times — so the work is O(n), not O(n²).

The key talking point: 'amortised, each element enters and leaves the window exactly once.'