Sliding windows: fixed and variable size

A sliding window is a stretch of consecutive items, from index left to index right, that moves along an array while a summary of what it holds, such as its total, is kept up to date. Instead of adding up every stretch from scratch, the window adds the item that enters on the right and removes the item that leaves on the left, so each step costs O(1). A fixed window always holds k items and answers questions such as the highest seven-day average. A variable window takes in items on the right and drops them from the left while a rule is broken, and answers questions such as the longest stretch within a budget. Both turn scans that cost O(n·k) or O(n²) into O(n). This lesson builds both in Python, traces them on small inputs and names the inputs on which a window gives wrong answers.

Fixed windows: one item in, one item out

A fixed window of k readings ends at right and holds a[right − k + 1] to a[right]. Build the first total with k additions; after that, each step adds the reading that enters and subtracts the one that leaves, total += a[right] − a[right − k]. Over n readings that is k + 2(n − k) additions, against (n − k + 1) × k for adding every window from scratch, so the cost of a step no longer depends on k. The program finds the highest seven-day average in 60 days of synthetic air-quality readings both ways:

"""The highest 7-day average of 60 days of air-quality readings (synthetic), by brute force and with a fixed window."""

import random

rng = random.Random(42)
aqi = [max(20, round(110 + 60 * rng.uniform(-1, 1) + (40 if 30 <= d < 40 else 0))) for d in range(60)]
K = 7
print("first 14 days:", aqi[:14])


def brute(a, k):
    """Adds up every window of k days from scratch."""
    best, adds = None, 0
    for start in range(len(a) - k + 1):
        total = 0
        for d in range(start, start + k):
            total += a[d]
            adds += 1
        if best is None or total > best[0]:
            best = (total, start)
    return best, adds


def window(a, k, trace=0):
    """Keeps one total: each step adds the day that enters and subtracts the day that leaves."""
    total = sum(a[:k])
    adds = k
    best = (total, 0)
    for right in range(k, len(a)):
        total += a[right] - a[right - k]  # day `right` enters, day `right - k` leaves
        adds += 2
        if total > best[0]:
            best = (total, right - k + 1)
        if right < k + trace:
            print(f"  day {right:>2} enters (+{a[right]}), day {right - k:>2} leaves (-{a[right - k]}): total {total}")
    return best, adds


(b_total, b_start), b_adds = brute(aqi, K)
print("the first steps of the window:")
(w_total, w_start), w_adds = window(aqi, K, trace=3)
print(f"brute force: best total {b_total} from day {b_start}, {b_adds} additions")
print(f"window:      best total {w_total} from day {w_start}, {w_adds} additions")
print(f"highest 7-day average: {w_total / K:.1f}, days {w_start} to {w_start + K - 1}")

first 14 days: [127, 53, 83, 77, 138, 131, 157, 60, 101, 54, 76, 111, 53, 74]
the first steps of the window:
  day  7 enters (+60), day  0 leaves (-127): total 699
  day  8 enters (+101), day  1 leaves (-53): total 747
  day  9 enters (+54), day  2 leaves (-83): total 718
brute force: best total 1207 from day 30, 378 additions
window:      best total 1207 from day 30, 113 additions
highest 7-day average: 172.4, days 30 to 36

Both find days 30 to 36, with an average of 172.4, but the window needed 113 additions where the brute force needed 378. The gap grows with k: for a 30-day window over a year of daily readings, the brute force makes 10,080 additions and the window 700.

Variable windows: grow on the right, shrink on the left

A courier firm logs the delay of every delivery in minutes, never negative, and wants the longest run of consecutive deliveries whose delays add up to at most a budget B. A variable window answers it in one pass:

1. Move right on by one and add its delay to total.
2. While total > B, subtract delays[left] and move left on.
3. The run from left to right is now the longest run within budget that ends at right; compare its length with the best so far.

Step 3 relies on a monotone rule. Delays are never negative, so a run within budget stays within budget when it loses deliveries at either end, and the deliveries left of left can be dropped for good. Here is the trace with a budget of 8:

"""The longest run of consecutive deliveries whose delays add up to at most a budget, with a variable window."""

import random


def longest_within(delays, budget, trace=False):
    """(length, first) of the longest run with total delay <= budget; delays are never negative."""
    left, total = 0, 0
    best = (0, 0)
    for right, d in enumerate(delays):
        total += d  # the delivery at `right` enters
        while total > budget:  # over budget: drop deliveries from the left until the run fits again
            total -= delays[left]
            left += 1
        if right - left + 1 > best[0]:
            best = (right - left + 1, left)
        if trace:
            print(f"  right {right}: +{d:<2} window {left}..{right}  total {total:>2}  best {best}")
    return best


def brute(delays, budget):
    best = (0, 0)
    for i in range(len(delays)):
        total = 0
        for j in range(i, len(delays)):
            total += delays[j]
            if total <= budget and j - i + 1 > best[0]:
                best = (j - i + 1, i)
    return best


log = [4, 1, 0, 6, 2, 3, 0, 1, 9, 2]
print(f"delays {log}, budget 8:")
print("result:", longest_within(log, 8, trace=True))

rng = random.Random(1)
cases = [([rng.randint(0, 9) for _ in range(rng.randint(0, 20))], rng.randint(0, 20)) for _ in range(2000)]
print("matches the brute force on 2,000 random logs:", all(longest_within(d, b) == brute(d, b) for d, b in cases))

delays [4, 1, 0, 6, 2, 3, 0, 1, 9, 2], budget 8:
  right 0: +4  window 0..0  total  4  best (1, 0)
  right 1: +1  window 0..1  total  5  best (2, 0)
  right 2: +0  window 0..2  total  5  best (3, 0)
  right 3: +6  window 1..3  total  7  best (3, 0)
  right 4: +2  window 2..4  total  8  best (3, 0)
  right 5: +3  window 4..5  total  5  best (3, 0)
  right 6: +0  window 4..6  total  5  best (3, 0)
  right 7: +1  window 4..7  total  6  best (4, 4)
  right 8: +9  window 9..8  total  0  best (4, 4)
  right 9: +2  window 9..9  total  2  best (4, 4)
result: (4, 4)
matches the brute force on 2,000 random logs: True

At right = 3 the total reaches 11, so the 4 leaves. At right = 8 a single delay of 9 is over the budget on its own, so the window empties until the next delivery. The answer is a run of 4 deliveries starting at position 4. The while loop inside the for loop does not make the scan quadratic: right moves n times, and left moves forward at most n times in total and never back, so the whole scan is at most 2n moves, O(n).

When a window is the wrong tool

Shrinking is safe only when a shorter window keeps a valid window valid. These inputs need something else:

• Negative values. A total can rise again after it falls, so dropping items on the left can lose the answer.
• Exact totals, any signs. Prefix sums with a hash map count the stretches whose total equals a target in one pass.
• The shortest stretch reaching a target, any signs. Prefix sums with a monotonic deque find it in O(n).
• Distinct values. A window over letters or labels keeps a dictionary of counts and deletes a key at count 0.

Timed drills on many window problems are in the sliding window patterns of Coding Interview Patterns.

Exercise: the shortest run that reaches a target

def shortest_run(footfall, target):
    """Length of the shortest run of consecutive shops with total footfall >= target, or 0 if there is none."""
    # Replace this line with your code.
    return 0

import random

from footfall import shortest_run


def brute(footfall, target):
    best = 0
    for i in range(len(footfall)):
        total = 0
        for j in range(i, len(footfall)):
            total += footfall[j]
            if total >= target:
                if best == 0 or j - i + 1 < best:
                    best = j - i + 1
                break
    return best


def test_examples():
    """the two streets of the prompt"""
    assert shortest_run([120, 40, 300, 80, 0, 90, 260], 350) == 2
    assert shortest_run([50, 50], 101) == 0


def test_small_streets():
    """an empty street, one shop that is enough, one that is not, and a target met only by the whole street"""
    assert shortest_run([], 5) == 0
    assert shortest_run([500], 500) == 1
    assert shortest_run([499], 500) == 0
    assert shortest_run([1, 2, 3, 4], 10) == 4
    assert shortest_run([0, 0, 7, 0, 0], 7) == 1


def test_random_streets():
    """300 random streets with zeros, against the brute force"""
    rng = random.Random(21)
    for _ in range(300):
        footfall = [rng.choice([0, 0, 1, 2, 5, 9]) for _ in range(rng.randint(0, 30))]
        target = rng.randint(1, 40)
        assert shortest_run(footfall, target) == brute(footfall, target), (footfall, target)


def test_long_street():
    """200,000 shops, which only a linear solution handles in time"""
    footfall = [k % 10 for k in range(200_000)]
    assert shortest_run(footfall, 45) == 9
    assert shortest_run(footfall, 10 ** 9) == 0

/** Length of the shortest run of consecutive shops with total footfall >= target, or 0 if there is none. */
export function shortestRun(footfall, target) {
  // Replace this line with your code.
  return 0;
}

import { test, assert } from 'mysmartcopilot:test';
import { shortestRun } from './footfall.mjs';

function brute(footfall, target) {
  let best = 0;
  for (let i = 0; i < footfall.length; i++) {
    let total = 0;
    for (let j = i; j < footfall.length; j++) {
      total += footfall[j];
      if (total >= target) {
        if (best === 0 || j - i + 1 < best) best = j - i + 1;
        break;
      }
    }
  }
  return best;
}

test('the two streets of the prompt', () => {
  assert.equal(shortestRun([120, 40, 300, 80, 0, 90, 260], 350), 2);
  assert.equal(shortestRun([50, 50], 101), 0);
});

test('an empty street, one shop that is enough, one that is not, and a target met only by the whole street', () => {
  assert.equal(shortestRun([], 5), 0);
  assert.equal(shortestRun([500], 500), 1);
  assert.equal(shortestRun([499], 500), 0);
  assert.equal(shortestRun([1, 2, 3, 4], 10), 4);
  assert.equal(shortestRun([0, 0, 7, 0, 0], 7), 1);
});

test('300 random streets with zeros, against the brute force', () => {
  let seed = 21;
  const random = () => (seed = (seed * 48271) % 2147483647) / 2147483647;
  const choices = [0, 0, 1, 2, 5, 9];
  for (let k = 0; k < 300; k++) {
    const footfall = Array.from({ length: Math.floor(random() * 31) }, () => choices[Math.floor(random() * choices.length)]);
    const target = 1 + Math.floor(random() * 40);
    assert.equal(shortestRun(footfall, target), brute(footfall, target), JSON.stringify([footfall, target]));
  }
});

test('200,000 shops, which only a linear solution handles in time', () => {
  const footfall = Array.from({ length: 200000 }, (_, k) => k % 10);
  assert.equal(shortestRun(footfall, 45), 9);
  assert.equal(shortestRun(footfall, 10 ** 9), 0);
});

Why the variable window is right and O(n), in five languages Pro: opens with a Pro, Premium or Ultimate pass

Windows over letters and labels: counts, a slip and the cost of hashing Pro: opens with a Pro, Premium or Ultimate pass

When windows fail: negative values reproduced, and two prefix-sum fixes Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

Key takeaways

• A sliding window keeps a summary of a stretch up to date as items enter on the right and leave on the left.
• A fixed window of k items adds one item and subtracts one per step, k + 2(n − k) additions in all.
• A variable window grows on the right and shrinks from the left while a rule is broken; left never moves back, so the scan is O(n).
• The variable window needs a monotone rule: with negative values, rules about totals call for prefix sums instead.