Sliding Window
A contiguous range that moves along a sequence, carrying a running summary that is repaired rather than recomputed.
A lot of questions about a sequence are really questions about every contiguous range of it: the largest sum of k consecutive values, the shortest stretch containing all of a required set, the longest run with no repeated character. Evaluating each range from scratch costs O(n * k) or O(n^2), and nearly all of that work is a recomputation of the previous range.
A window fixes that by keeping the summary of the current range and editing it. When the right edge advances, add the element that entered; when the left edge advances, subtract the element that left. Each index enters once and leaves once, so the whole scan is O(n) even though the two edges move independently and the inner shrink loop looks nested.
There are two shapes. A fixed window of size k moves both edges together and its summary is usually a single number, so the space is O(1). A variable window grows the right edge until some condition holds, then pulls the left edge in while the condition still holds; its summary is often a frequency map, O(k) space or O(alphabet) for text. The variable form needs the condition to be monotone in the window: extending the window must never repair a violation, or the shrink step is answering the wrong question.
After this you can
- Turn a nested loop over all contiguous ranges into a single pass with two edges
- Write the add step and the remove step so the summary is correct at every position
- Tell a fixed-size window problem from a variable-size one by reading the question
- Use a frequency map inside the window to answer at-most-k-distinct and covers-all questions
- Argue why the scan is O(n) even though the left edge moves inside the loop
2 leaves and 1 enters, so the sum is 7. The best stays at 8.
In this order
- Sliding WindowKeep a contiguous range and update its summary as it moves, instead of rescanning it.
- Fixed-Size WindowA window of size k. Add what enters, subtract what leaves, never re-add the middle.
- Maximum Sum Subarray of Size kSlide a fixed window across the array and keep the best sum it ever held.
- Variable-Size WindowGrow the right end until a condition holds, then shrink the left end while it still does.
- Frequency Map + WindowTrack counts of what is inside the window to answer "at most k distinct" style questions.
- Longest Substring Without Repeating CharactersVariable window plus the last index of each character; a repeat inside jumps the left edge past its earlier copy.
- Minimum Window SubstringExpand until the window covers all required characters, then shrink while it still does.
Where people go wrong
Off by one at the edges
With a half-open window the size is right - left and the element just admitted sits at right - 1; with a closed window the size is right - left + 1. Both work, but the first complete window arrives at a different index under each, so mixing the two conventions inside one function is the usual cause of a missing first or last answer.
Shrinking with an if instead of a while
One element entering on the right can make the window invalid by more than one removal, especially when duplicates arrive. An if removes a single element and then reports a window that was never valid; the shrink has to be a loop that runs until the condition holds again.
Sliding over negative numbers
The shrink step assumes removing an element can only move the summary one way. With negative values a shorter range can have a larger sum, so shrink-while-the-sum-is-too-big never settles on the right answer. Those problems want a prefix sum or Kadane instead of a window.
Or a different category
Two Pointers
The two indices walk toward each other over a sorted array rather than tracking one range that sweeps left to right.
Range Queries
The ranges are handed to you by arbitrary queries rather than swept once in order, so a prefix sum or a segment tree is what answers them.