A sliding window maintains a contiguous range over an array — defined by left and right pointers — and slides it forward, updating the answer incrementally. The point is to avoid re-scanning the same elements every time the window shifts.
Fixed-size window
Compute an aggregate (sum, max, average) over every window of size . After computing the first window's aggregate in , each subsequent window costs : subtract the element that left, add the element that entered. Total cost: instead of .
Variable-size window
The window grows or shrinks based on a condition. Typical pattern:
- Expand the right pointer to include more elements while the window is valid
- When the window becomes invalid, shrink the left pointer until it's valid again
- Track the best answer seen so far
This is the structure for "longest substring with at most K distinct characters," "minimum window substring," and "longest subarray with sum ≤ K."
Why it's $O(n)$
Both pointers only move forward. Each element is visited at most twice — once when the right pointer admits it, once when the left pointer evicts it. That gives the total work bound.
Subtle trap
Sliding window assumes the property you're tracking is monotone in the window — extending the right side can only make the window "more violating," not less. If the property doesn't satisfy this (e.g., "exactly K distinct" on negative-valued arrays), you may need a different technique like prefix sums with a hash map.