Sliding Window
A window is a summary you maintain, not a range you rescan. When it slides, subtract what left and add what entered. That one idea turns a nested loop into a single pass.
Find the largest sum of 3 values in a row. The first window is indices 0 to 2, sum 8.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 5, with their answers.
2 leaves, 1 enters. Sum 7, best so far 8. Which?
Answer: Not better. 7 does not beat 8. The slide still cost one subtraction and one addition.
1 leaves, 3 enters. Sum 9, best so far 8. Which?
Answer: New best. 9 is larger than anything seen so far. One subtraction and one addition found it.
5 leaves, 2 enters. Sum 6, best so far 9. Which?
Answer: Not better. 6 does not beat 9. The slide still cost one subtraction and one addition.
1 leaves, 7 enters. Sum 12, best so far 9. Which?
Answer: New best. 12 is larger than anything seen so far. One subtraction and one addition found it.
3 leaves, 1 enters. Sum 10, best so far 12. Which?
Answer: Not better. 10 does not beat 12. The slide still cost one subtraction and one addition.
How it runs, step by step
Find the largest sum of 3 values in a row. The first window is indices 0 to 2, sum 8.
Finding the largest sum of 3 consecutive values. The first window covers indices 0 to 2.
2 leaves and 1 enters, so the sum is 7. The best stays at 8.
The window slides right. 2 leaves and 1 enters, giving a sum of 7. The best is still 8.
1 leaves and 3 enters, so the sum is 9. That beats the best so far.
The window slides right. 1 leaves and 3 enters, giving a sum of 9. That is a new best.
5 leaves and 2 enters, so the sum is 6. The best stays at 9.
The window slides right. 5 leaves and 2 enters, giving a sum of 6. The best is still 9.
1 leaves and 7 enters, so the sum is 12. That beats the best so far.
The window slides right. 1 leaves and 7 enters, giving a sum of 12. That is a new best.
3 leaves and 1 enters, so the sum is 10. The best stays at 12.
The window slides right. 3 leaves and 1 enters, giving a sum of 10. The best is still 12.
The best window is indices 4 to 6 with sum 12. 5 slides, each O(1), so O(n) overall.
The largest sum of 3 consecutive values is 12, at indices 4 to 6.
Write it yourself
Define maxWindowSum(values, k) and return the largest sum of any k values in a row. It runs in your browser against this lesson's own 3 examples.
// Add the first k, then slide: add what enters and subtract what leaves, rather than re-adding the window.function maxWindowSum(values, k) { return 0;}
Remember
- A fixed window updates in O(1): one value leaves, one enters, nothing is re-added.
- A variable window grows the right end until a condition holds, then shrinks the left while it still does.
- Both ends only ever move forward, which is why two nested-looking loops are still O(n).
Topics covered
Related
Where this is used
CompressionDEFLATE, the algorithm behind gzip and PNG
DEFLATE replaces a repeated run of bytes with a back-reference to an identical run seen earlier, but it only looks back inside a 32 KB window that slides forward with the cursor. Bounding the lookback is what keeps the encoder's match table small and the distance field in the output short. Anything older has fallen off the left edge and is no longer a candidate, which is why compressing a huge file needs no more memory than a small one.
NetworkingTCP flow control
A TCP sender may keep one window's worth of bytes unacknowledged in flight. Each acknowledgement advances the left edge and the right edge moves forward by the same amount, so the sender tracks two sequence numbers rather than the state of the whole stream. The receiver advertises a smaller window when its buffer fills, which is how a slow reader throttles a fast sender without the connection dropping data.
StorageThe rsync rolling checksum
rsync finds which parts of a file already exist on the other side by checksumming every window of block-size bytes, at every offset, not just at block boundaries. Its weak checksum is built to roll: the running sum over the window updates with one subtraction for the byte that left and one addition for the byte that entered, the same move as sum += a[right] - a[right - k], and a second position-weighted term is then derived from it in constant time. Without that, every offset would cost a full block-size rescan instead of constant work, and the same rolling trick drives content-defined chunking in deduplicating backup tools.
OperationsSliding window rate limits
A fixed per-minute counter lets a client spend a full quota at 11:59:59 and another at 12:00:00, so gateways anchor the window to now instead. The common Redis implementation keeps request timestamps in a sorted set, trims everything past the left edge with ZREMRANGEBYSCORE, then adds the new request at the right edge, so nothing still inside the window is ever recounted. Cloudflare's rate limiting uses the same shape but weights the previous fixed window rather than storing each timestamp, trading a little accuracy for constant memory per client.
Why it works this way
Why is the inner while loop still O(n)?
Count pointer moves, not nested iterations. left is incremented at most once per element over the whole call, and so is right, so the two ends make at most 2n moves in total however the input is arranged. One iteration of the outer loop may shrink the window many times, which is why per-iteration reasoning fails and the amortised count is the honest one.
Shrinking has to be safe, or the window is the wrong tool
shortestRunAtLeast stops shrinking the moment the sum falls under target, which assumes that removing an element can only lower the sum. One negative value breaks that: a shorter window can hold a larger sum, so a window the loop already walked past may be the real answer. Once negatives are allowed the two-pointer window no longer applies, and the problem is solved with prefix sums over a monotonic deque instead, still one pass but a different algorithm.
Some quantities cannot leave a window
Sum and count are invertible, so subtracting the departing element exactly undoes what adding it did. Maximum is not: once the largest value leaves, the old maximum says nothing about the new one and a rescan costs O(k), which is why sliding window maximum carries a deque of decreasing candidates rather than one number. Rolling averages over floating point sit in between, since add-then-subtract drifts as rounding error accumulates and long streams need a periodic recompute.
Seeding a fixed window: best = 0 is a bug
best has to start at the first window's sum. Seed it with 0 and an array of all negative numbers returns 0, which is not the sum of any window. The loop then starts at index k because every earlier position already sits inside that first window, and note that a.take(k) quietly returns fewer than k elements when k is larger than the array, so an unguarded call reports a short prefix as a valid window.
Read more
- Sliding window protocolWikipedia
- Minimum stack, minimum queuecp-algorithms
- Rolling hashWikipedia
- DEFLATE compressed data format specificationIETF RFC 1951 · datatracker.ietf.org
- The rsync algorithmTridgell and Mackerras · rsync.samba.org
Next up
- 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.