Intuition First: The Train Window#
Watching the landscape from a moving train, you never re-scan the whole countryside. A new strip of scenery slides into view on one side exactly as an old strip vanishes on the other. A sliding window works the same way over an array: as the window moves one step, you add the element that just entered and subtract the one that just left, instead of recomputing the entire range from scratch.
That tiny add-one, drop-one bookkeeping is the whole trick. It turns a problem where you'd re-sum every window (O(n²)) into a single smooth pass (O(n)).
The Concept#
A sliding window is a contiguous subarray described by two indices, left and right, that together define a range [left, right] inside a larger array. Instead of re-examining every element each time the window moves, you maintain a running aggregate, adding the element that just entered on the right and removing the one that just left on the left. That incremental update costs O(1) per step, which is what makes the whole scan O(n).
There are two distinct flavours, and knowing which one to reach for is the main skill.
Fixed-size window#
The window width is a constant k. You slide it one step at a time across the array:
- Compute the aggregate for the initial window
[0, k-1]. - For every new position, add
nums[right]and subtractnums[right - k], the element that fell off the left edge. - Track the best aggregate seen so far.
A canonical example: maximum sum of any subarray of length k. Because both indices advance monotonically and the update is O(1), the full scan is O(n) with O(1) extra space.
Variable-size window#
Here the window width is not fixed. It is bounded by a constraint (e.g. "at most k zeros", "sum ≤ target"). The strategy is:
- Grow
rightto include the next element. - While the constraint is violated, advance
leftto shrink the window until the constraint holds again. - At each step where the constraint holds, record the window size (or whatever you are optimizing).
A canonical example: longest subarray of 1s you can form by flipping at most k zeros (LeetCode 1004 / Max Consecutive Ones III variant). The key insight is that left never moves backwards (both pointers only advance), so the total number of steps across the entire scan is at most 2n, giving O(n) overall.
Code Implementation#
Complexity Analysis#
| Variant | Time | Space | Why |
|---|---|---|---|
| Fixed-size window | O(n) | O(1) | One pass; each element enters and leaves once |
| Variable-size window | O(n) | O(1) | Both pointers advance monotonically; total steps ≤ 2n |
The O(n) bound holds even for the variable-size variant despite the inner while loop. Because left never decreases, the total number of times it advances across the entire outer loop is at most n, so the inner and outer loops together take O(n) steps.
Interactive Lab#
Fixed-size: maximum sum of k consecutive elements#
Let's take the example in the visualization below: nums = [2, 1, 5, 1, 3, 2] with k = 3. There are only four windows, and the winner is not at either end.
The very first frame adds 2 + 1 + 5 = 8, and that is the only full summation in the entire run. Every step after it is one addition and one subtraction:
| Window | Update | Sum | Best so far |
|---|---|---|---|
[2, 1, 5] | built from scratch | 8 | 8 |
[1, 5, 1] | +1 (index 3), −2 (index 0) | 7 | 8 |
[5, 1, 3] | +3 (index 4), −1 (index 1) | 9 | 9 ← new best |
[1, 3, 2] | +2 (index 5), −5 (index 2) | 6 | 9 |
Watch the add-and-drop caption as you step: it names the element entering and the element leaving on every slide, alongside the Sum and Best chips. The green highlight jumps to [5, 1, 3] mid-scan and then has to survive one more window before the run ends. That is exactly why you track a running best rather than just reading off the last value.
Variable-size: smallest window whose sum reaches a target#
Same machinery, different stopping rule. Here the input is nums = [2, 3, 1, 2, 4, 3] with target = 7, and the question is the shortest contiguous run whose sum is at least 7.
Play it and watch the two edges take turns. right expands until the sum first reaches 7 at window [2, 3, 1, 2] (length 4). Then left advances to squeeze the window as small as it can while the sum still holds, and each time the sum drops below 7, right takes over again. The MinLen counter ratchets down 4 → 3 → 2, finishing on [4, 3].
Neither pointer ever moves backwards, which is the whole reason the nested-looking loop is still O(n).
Variable-size: longest run of 1s with at most k flips#
The constraint here is a budget rather than a sum: nums = [1, 1, 0, 0, 1, 1, 0, 1, 1, 1] with k = 2 zeros you are allowed to flip.
right swallows elements until the window holds a third zero. That happens at index 6, and the window is immediately illegal. left then advances until the zero count is back down to 2, dropping the two 1s at the front along with the zero at index 2. From there right runs clean to the end, finishing with the window [3..9] of length 7. The two zeros inside it are the two you spend your flips on.
The Zeros and MaxLen chips are the pair to watch: Zeros is the invariant being defended, MaxLen is the answer being accumulated.
What to Remember#
- Window invariant. At every step the window
[left, right]satisfies the problem's constraint. Maintaining that invariant, not just checking it after the fact, is what makes the approach correct and efficient. - Fixed vs. variable. Fixed-size windows update with a single add-and-subtract. Variable-size windows grow on the right and shrink on the left until the constraint holds; the constraint drives
left, not a fixed offset. - Each element enters and leaves once → linear time.
rightsweeps from 0 to n-1 exactly once.leftonly ever advances. The total number of index movements is at most 2n regardless of how many times the inner shrink loop runs. - O(1) extra space. Both patterns only track a constant number of running values (sum, zero count, etc.), so no auxiliary array is needed.