🪟 Sliding Window

Sliding Window is what happens when you notice that two overlapping subarrays share almost all their work. Brute force recomputes each range from scratch; a window keeps a running summary (a sum, a count map, a max) and updates it in O(1) as one element enters and another leaves.

It's the highest-leverage pattern in interviews for one reason: an enormous class of "longest / shortest / count of substrings or subarrays satisfying X" questions collapse to the same dozen lines once you see the window.

• The answer is about a contiguous range — substring, subarray — never a subsequence (that's usually DP).
• Words like "longest", "shortest", "at most K", "exactly K", "maximum sum of size k".
• The brute force enumerates O(n²) ranges and re-scans each one.
• The validity of a window can be tracked incrementally — adding or removing one element updates the state cheaply.

• Fixed-size windows: max/min/average of every k-length subarray — slide and update.
• Variable-size windows: grow the right edge greedily, shrink from the left only when the window breaks a constraint.
• Frequency-map windows: anagram and "contains all characters of t" problems, where the state is a count map plus a satisfied-counter.
• "At most K distinct / at most K replacements" problems, where the shrink condition is a budget.

Write the loop the same way every time: for each right in 0..n, admit s[right] into the window state; then, while the window is invalid, evict s[left] and advance left; then record the answer from the current (valid) window. Grow eagerly, shrink lazily, measure when legal.

The crucial invariant: left never moves backward. Both pointers travel at most n steps across the whole run, which is why the nested-looking while inside a for is still O(n) — amortize the shrinking over the run, not per iteration.

If shrinking can't restore validity incrementally — if you'd have to rescan the window to know — the window summary you chose is too weak. Strengthen the state (add a count map, a satisfied-counter, a monotonic deque) before abandoning the pattern.

O(n) time — each element enters and leaves the window exactly once. Space is O(1) for numeric summaries or O(k) for a frequency map over the alphabet/window.

• Applying it to problems with negative numbers where "growing makes the sum bigger" stops being true — the monotonic reasoning breaks (see Minimum Size Subarray Sum vs. its negative-number cousins).
• Updating the answer before restoring validity — decide whether you measure valid windows (usual) or after each admit, and be consistent.
• Rebuilding the window state from scratch on shrink — the whole point is the O(1) incremental update.
• Confusing subsequence with substring in the problem statement, then wondering why the window never fits.

In this order, on LeetCode. Each one adds a wrinkle the previous one didn't have.

1. 1#121 Best Time to Buy and Sell StockEasy
2. 2#3 Longest Substring Without Repeating CharactersMedium
3. 3#424 Longest Repeating Character ReplacementMedium
4. 4#567 Permutation in StringMedium
5. 5#209 Minimum Size Subarray SumMedium
6. 6#76 Minimum Window SubstringHard
7. 7#239 Sliding Window MaximumHard