Sliding Window
Grow and shrink a contiguous range to track a running property in O(n).
The idea
A sliding window maintains a contiguous sub-range of an array or string and moves its two edges to answer questions about subarrays without recomputing from scratch. The window is defined by two indices — usually `left` and `right` — and some running state (a sum, a count, a set).
The key insight: instead of re-scanning every subarray (which is O(n²) or worse), you *reuse* work. When you extend `right`, you add one element to the state; when a constraint breaks, you advance `left` to restore it. Each index enters and leaves the window at most once, so the whole scan is O(n).
Picture a train window as the train moves. You only ever see the passengers currently framed by the window — as new ones scroll into view on the right, old ones leave on the left. You never re-count everyone from the front of the train.
When to reach for it
- The problem asks about a contiguous subarray or substring.
- You want the longest / shortest / max / min range satisfying a constraint.
- A brute-force answer recomputes overlapping subranges repeatedly.
Language-independent template
left = 0
state = empty
for right in range(n):
add arr[right] to state
while window is invalid:
remove arr[left] from state
left += 1
update answer using (right - left + 1)Complexity — time O(n), space O(k) (k = distinct elements inside the window).
Common mistakes
- Shrinking with an
ifinstead of awhile— the window may still be invalid after one step. - Updating the answer before restoring the window's validity.
- Forgetting to remove the leaving element from the running state when
leftadvances.
Practice progression
Canonical interview problems, ordered from foundation to advanced application.
Find the maximum average among subarrays of a fixed size.
Find the longest substring containing no repeated character.
Find the smallest substring covering all required characters.