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 shortest run of values whose sum reaches 7. Grow the right end until the sum is enough, then shrink the left end while it still is.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 11, with their answers.
Sum is 2, target is 7. What happens next?
Answer: Grow right. The sum is short, and shrinking would only make it shorter. Only growing can help.
Sum is 5, target is 7. What happens next?
Answer: Grow right. The sum is short, and shrinking would only make it shorter. Only growing can help.
Sum is 6, target is 7. What happens next?
Answer: Grow right. The sum is short, and shrinking would only make it shorter. Only growing can help.
Sum is 8, target is 7. What happens next?
Answer: Shrink left. The sum is enough. The only way to find something shorter is to shrink from the left.
Sum is 6, target is 7. What happens next?
Answer: Grow right. Dropped below the target, so the window has to grow again.
Sum is 10, target is 7. What happens next?
Answer: Shrink left. The sum is enough. The only way to find something shorter is to shrink from the left.
Sum is 7, target is 7. What happens next?
Answer: Shrink left. Still enough, so there may be an even shorter run. Keep shrinking.
Sum is 6, target is 7. What happens next?
Answer: Grow right. Dropped below the target, so the window has to grow again.
Sum is 9, target is 7. What happens next?
Answer: Shrink left. The sum is enough. The only way to find something shorter is to shrink from the left.
Sum is 7, target is 7. What happens next?
Answer: Shrink left. Still enough, so there may be an even shorter run. Keep shrinking.
Sum is 3, target is 7. What happens next?
Answer: Grow right. Dropped below the target, so the window has to grow again.
How it runs, step by step
Find the shortest run of values whose sum reaches 7. Grow the right end until the sum is enough, then shrink the left end while it still is.
Finding the shortest contiguous run with a sum of at least 7.
Grow right to index 0. 2 joins, so the sum is 2. Still short of 7.
The right end moves to index 0 and the sum becomes 2. That is still below the target.
Grow right to index 1. 3 joins, so the sum is 5. Still short of 7.
The right end moves to index 1 and the sum becomes 5. That is still below the target.
Grow right to index 2. 1 joins, so the sum is 6. Still short of 7.
The right end moves to index 2 and the sum becomes 6. That is still below the target.
Grow right to index 3. 2 joins, so the sum is 8. That reaches 7, so the left end can start shrinking.
The right end moves to index 3 and the sum becomes 8. That reaches the target.
Length 4 is the best so far. Drop 2 from the left, leaving 6. Now short of 7, so grow right next.
The left end moves to index 1, dropping 2. The sum is 6. It no longer reaches the target.
Grow right to index 4. 4 joins, so the sum is 10. That reaches 7, so the left end can start shrinking.
The right end moves to index 4 and the sum becomes 10. That reaches the target.
Length 4 is no better than 4. Drop 3 from the left, leaving 7. Still enough, so shrink again.
The left end moves to index 2, dropping 3. The sum is 7. It still reaches the target.
Length 3 is the best so far. Drop 1 from the left, leaving 6. Now short of 7, so grow right next.
The left end moves to index 3, dropping 1. The sum is 6. It no longer reaches the target.
Grow right to index 5. 3 joins, so the sum is 9. That reaches 7, so the left end can start shrinking.
The right end moves to index 5 and the sum becomes 9. That reaches the target.
Length 3 is no better than 3. Drop 2 from the left, leaving 7. Still enough, so shrink again.
The left end moves to index 4, dropping 2. The sum is 7. It still reaches the target.
Length 2 is the best so far. Drop 4 from the left, leaving 3. Now short of 7, so grow right next.
The left end moves to index 5, dropping 4. The sum is 3. It no longer reaches the target.
The shortest run is indices 4 to 5, length 2. Each end moved only forward, 11 moves in all, so O(n).
The shortest run with sum at least 7 has length 2.
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.