AlgoScope

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.

The player

Finding the largest sum of 3 consecutive values. The first window covers indices 0 to 2.active 0-22011521334257617leftright

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.

  1. 2 leaves, 1 enters. Sum 7, best so far 8. Which?

    • New best
    • Not better

    Answer: Not better. 7 does not beat 8. The slide still cost one subtraction and one addition.

  2. 1 leaves, 3 enters. Sum 9, best so far 8. Which?

    • New best
    • Not better

    Answer: New best. 9 is larger than anything seen so far. One subtraction and one addition found it.

  3. 5 leaves, 2 enters. Sum 6, best so far 9. Which?

    • New best
    • Not better

    Answer: Not better. 6 does not beat 9. The slide still cost one subtraction and one addition.

  4. 1 leaves, 7 enters. Sum 12, best so far 9. Which?

    • New best
    • Not better

    Answer: New best. 12 is larger than anything seen so far. One subtraction and one addition found it.

  5. 3 leaves, 1 enters. Sum 10, best so far 12. Which?

    • New best
    • Not better

    Answer: Not better. 10 does not beat 12. The slide still cost one subtraction and one addition.

How it runs, step by step

  1. 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. 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.

  3. 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.

  4. 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.

  5. 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.

  6. 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.

  7. 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.

The code

Sliding Window, in Python

def max_sum_of_size(a, k):
    window_sum = sum(a[:k])
    best = window_sum
    for right in range(k, len(a)):
        window_sum += a[right] - a[right - k]
        best = max(best, window_sum)
    return best

def shortest_run_at_least(a, target):
    left = 0
    window_sum = 0
    best = float('inf')
    for right in range(len(a)):
        window_sum += a[right]
        while window_sum >= target:
            best = min(best, right - left + 1)
            window_sum -= a[left]
            left += 1
    return best

Sliding Window, in JavaScript

function maxSumOfSize(a, k) {
  let sum = a.slice(0, k).reduce((acc, v) => acc + v, 0);
  let best = sum;
  for (let right = k; right < a.length; right++) {
    sum += a[right] - a[right - k];
    best = Math.max(best, sum);
  }
  return best;
}

function shortestRunAtLeast(a, target) {
  let left = 0;
  let sum = 0;
  let best = Infinity;
  for (let right = 0; right < a.length; right++) {
    sum += a[right];
    while (sum >= target) {
      best = Math.min(best, right - left + 1);
      sum -= a[left++];
    }
  }
  return best;
}

Sliding Window, in Kotlin

fun maxSumOfSize(a: IntArray, k: Int): Int {
    var sum = a.take(k).sum()
    var best = sum
    for (right in k until a.size) {
        sum += a[right] - a[right - k]
        best = max(best, sum)
    }
    return best
}

fun shortestRunAtLeast(a: IntArray, target: Int): Int {
    var left = 0; var sum = 0; var best = Int.MAX_VALUE
    for (right in a.indices) {
        sum += a[right]
        while (sum >= target) {
            best = min(best, right - left + 1)
            sum -= a[left++]
        }
    }
    return best
}

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;}
6 linesTab indents. Escape, then Tab, leaves the editor. Ctrl-Enter runs (Cmd-Enter on a Mac).

    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).

    Where this is used

    DEFLATE, the algorithm behind gzip and PNGCompression

    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.

    TCP flow controlNetworking

    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.

    The rsync rolling checksumStorage

    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.

    Sliding window rate limitsOperations

    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

    Next up

    Frequency Map Window

    At most 2 distinct

    Next lesson: Frequency Map Window