What it is
A sliding window keeps a contiguous range of a sequence (an array, a string, or a stream of timestamped events) between two pointers and moves those pointers forward as some condition changes, so the window only ever expands on the right and contracts on the left. The payoff is turning an O(n²) "check every subarray" approach into O(n), because the window's running state (a sum, a character count map, a count of distinct values) is updated incrementally rather than recomputed from scratch each time the window changes.
When it applies
- You need the longest, shortest, or a count of contiguous subarrays/substrings satisfying a condition that gets easier to check as you add or remove one element at a time (a sum threshold, a count of a value, a distinct-character limit).
- You're tracking events or requests inside a trailing time window, where old entries expire as new ones arrive.
- Negative numbers in the array break a sum-based window's monotonic in/out relationship, so prefix sums with a hash map are needed instead; and subarrays that don't need to be contiguous belong to a different pattern (subsets, subsequences) entirely.
Tells in the problem
- "Contiguous subarray" or "substring" paired with a sum, count, or distinct-value constraint.
- "At most k distinct characters," "longest without repeating," or "shortest subarray with sum at least."
- A trailing time window ("hits in the last 300 seconds," "requests per minute").
- "Exactly k" of something — often solved by taking "at most k" minus "at most k-1," rather than tracking exactness directly.
The classic mistake
The window's internal state and its length get out of sync: a solution grows the right pointer, updates a frequency map, but only shrinks the left pointer far enough to make the window "look" valid without re-checking that every count is still within bounds, so it silently accepts a window with e.g. three distinct characters when the limit was two. This shows up as an off-by-one in the answer that only appears on inputs where the window needs to shrink by more than one step at once. The fix is to shrink in a while loop that re-checks the actual condition after each removal, not an if that assumes one step is enough — and to update the running state (decrementing a count, possibly deleting a key at zero) on every removal, not just moving the pointer.
Questions to start with
- Longest Substring Without Repeating Characters — the canonical variable-size window: grow, and shrink only when a duplicate appears.
- Minimum Size Subarray Sum — a window driven by a numeric sum instead of a character set, shrinking greedily once the target is met.
- Longest Substring with At Most K Distinct Characters — the "at most k" shape that several trickier problems reduce to.
- Fruit Into Baskets — the same "at most k distinct" idea in a different costume (k fixed at two).
- Longest Repeating Character Replacement — the window condition becomes "majority count plus k edits," not a simple distinct-count check.
- Minimum Window Substring — the hardest variant: the window must satisfy a multiset of required counts, not just a size or distinct limit.
- Sliding Window Maximum — a fixed-size window where the per-step work itself needs a monotonic deque to stay O(n).