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 shortest contiguous run with a sum of at least 7.203112234435

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.

  1. Sum is 2, target is 7. What happens next?

    • Grow right
    • Shrink left

    Answer: Grow right. The sum is short, and shrinking would only make it shorter. Only growing can help.

  2. Sum is 5, target is 7. What happens next?

    • Grow right
    • Shrink left

    Answer: Grow right. The sum is short, and shrinking would only make it shorter. Only growing can help.

  3. Sum is 6, target is 7. What happens next?

    • Grow right
    • Shrink left

    Answer: Grow right. The sum is short, and shrinking would only make it shorter. Only growing can help.

  4. Sum is 8, target is 7. What happens next?

    • Grow right
    • Shrink left

    Answer: Shrink left. The sum is enough. The only way to find something shorter is to shrink from the left.

  5. Sum is 6, target is 7. What happens next?

    • Grow right
    • Shrink left

    Answer: Grow right. Dropped below the target, so the window has to grow again.

  6. Sum is 10, target is 7. What happens next?

    • Grow right
    • Shrink left

    Answer: Shrink left. The sum is enough. The only way to find something shorter is to shrink from the left.

  7. Sum is 7, target is 7. What happens next?

    • Grow right
    • Shrink left

    Answer: Shrink left. Still enough, so there may be an even shorter run. Keep shrinking.

  8. Sum is 6, target is 7. What happens next?

    • Grow right
    • Shrink left

    Answer: Grow right. Dropped below the target, so the window has to grow again.

  9. Sum is 9, target is 7. What happens next?

    • Grow right
    • Shrink left

    Answer: Shrink left. The sum is enough. The only way to find something shorter is to shrink from the left.

  10. Sum is 7, target is 7. What happens next?

    • Grow right
    • Shrink left

    Answer: Shrink left. Still enough, so there may be an even shorter run. Keep shrinking.

  11. Sum is 3, target is 7. What happens next?

    • Grow right
    • Shrink left

    Answer: Grow right. Dropped below the target, so the window has to grow again.

How it runs, step by step

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

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

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

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

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

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

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

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

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

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

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

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

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

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