Sliding Window
Maintain a moving range over a sequence, expanding and contracting it to answer "best/longest/shortest contiguous …" questions in linear time.
Key ideas
- —Grow the window to include new elements; shrink it when it violates a constraint.
- —Track just enough state (a sum, a count, a frequency map) to update in O(1) per step.
- —Fixed-size vs variable-size windows are two distinct templates — know both.
When it applies
Use a sliding window for problems about contiguous subarrays or substrings: longest substring without repeats, smallest subarray with a target sum, max average of k elements. The window represents the current candidate, and you slide its bounds instead of recomputing from scratch.
The two templates
Fixed window: advance both ends together, updating aggregate state as one element enters and one leaves. Variable window: expand the right end greedily, then advance the left end only while a constraint is violated. The amortized cost is O(n) because each element enters and leaves the window at most once.
Practice this
Sources
- Window Sliding TechniqueGeeksforGeeks
- collections.Counter / deque (window state)Python docs