Sliding Window
Sliding window answers questions about ranges of consecutive items - "the best k days of sales", "the longest substring with no repeats" - without recomputing each range from scratch. The insight: two neighbouring ranges overlap almost completely, so when the range slides one step, just add the new item and remove the old one. What looks like O(n·k) work collapses into a single O(n) pass.
Watch the window slide
Press play - or drag the timeline and step through it yourself.Find the biggest sum of 4 values in a row. The slow way checks every group from scratch - the window way reuses the overlap.
Complexity
A train window
You are on a slow train counting cows in the fields. Someone asks: "What was the most cows visible in any single minute?" You do not re-count the whole field every second. As the view slides, a few cows enter on one side and a few leave on the other - you adjust your count by the difference. Your running count is always correct, and you never counted any cow more than twice: once entering the view, once leaving it.
How it works, step by step
Compute the answer for the first window - the first k values - the normal way.
Slide the window one step right: one value enters on the right, one leaves on the left.
Update the running result with just those two changes: add the newcomer, subtract the leaver.
Compare with the best result seen so far and remember the winner.
Repeat until the window reaches the end. Each value enters once and leaves once - that is 2n operations, so O(n).
For "longest range satisfying a rule" problems the window also grows and shrinks - the right edge extends, and the left edge catches up whenever the rule breaks.
The code, in JavaScript
The fixed-size shape: best sum of k consecutive values. One pass; the window is just two numbers of bookkeeping.
function maxWindowSum(arr, k) {
if (arr.length < k) return null;
// Sum of the first window, computed once.
let sum = 0;
for (let i = 0; i < k; i++) sum += arr[i];
let best = sum;
for (let i = k; i < arr.length; i++) {
sum += arr[i] - arr[i - k]; // add newcomer, drop leaver
best = Math.max(best, sum);
}
return best;
}
maxWindowSum([4, 2, 9, 7, 5, 3], 2); // → 16 (9 + 7)Dry run: best 2-value window in [4, 2, 9, 7, 5, 3]
The same steps the visualizer plays, written as a table. Generated by running the real algorithm - not written by hand.
| Step | Window | Array | What happened |
|---|---|---|---|
| 1 | 1 | [4, 2, 9, 7, 5, 3] | Build the first window: add 4 - sum so far 4. |
| 2 | 1 | [4, 2, 9, 7, 5, 3] | Build the first window: add 2 - sum so far 6. |
| 3 | 2 | [4, 2, 9, 7, 5, 3] | Slide: drop 4, add 9 - new sum 11. Better than 6 - new best! |
| 4 | 3 | [4, 2, 9, 7, 5, 3] | Slide: drop 2, add 7 - new sum 16. Better than 11 - new best! |
| 5 | 4 | [4, 2, 9, 7, 5, 3] | Slide: drop 9, add 5 - new sum 12. Best stays 16. |
| 6 | 5 | [4, 2, 9, 7, 5, 3] | Slide: drop 7, add 3 - new sum 8. Best stays 16. |
Good choice when…
- The question is about consecutive items: best k-day stretch, longest substring with a property, shortest run reaching a target.
- A brute-force answer would recompute overlapping ranges - the overlap is exactly what the window reuses.
- You process a stream and only ever need a summary of the recent past (moving averages, rate limiting) - the window never looks back.
- Both edges of the range only move forward - that is the signature that one O(n) pass suffices.
Bad choice when…
- The items in the range need not be consecutive (subsequences, not substrings) - a window cannot represent gaps; that is DP territory.
- Negative numbers break the shrink logic in sum-target problems - "add more" no longer guarantees "sum grows", so the greedy shrink is unsound (use prefix sums instead).
- The window property cannot be updated incrementally - if removing an item forces a full recompute (like a median without extra structures), the O(n) advantage disappears.
Common mistakes
- The window works because updates are incremental: add one, remove one, O(1). If you find yourself re-scanning the window's contents inside the loop, you are back to O(n·k) with extra steps.
- In variable-size problems the left edge must never move backwards. If your logic can move `left` left, the two-edges-forward argument dies and so does the O(n) bound.
- When shrinking on repeats, jump `left` to `lastSeen + 1`, not `left + 1` - creeping one step at a time re-admits the duplicate and produces subtly wrong lengths.
- "Longest subarray" and "longest subsequence" read almost the same and are completely different problems. Windows solve subarrays (consecutive); subsequences (with gaps) need dynamic programming.
Sliding Window vs. its closest relatives
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Sliding Windowthis page | O(n) | O(n) | O(n) | O(k) | - |
| Two Pointers | O(n) | O(n) | O(n) | O(1) | - |
| Kadane's Algorithm | O(n) | O(n) | O(n) | O(1) | - |
| Linear Search | O(1) | O(n) | O(n) | O(1) | - |