The Sliding Window

The sliding window

A huge family of real questions asks about every consecutive range of a sequence: the busiest 3-day stretch in a metrics dashboard, the most requests in any 60-second span of a server log, the longest run of distinct items. These power monitoring alerts and rate limiters, and they are one of the most common interview shapes.

The naive plan recomputes each range from scratch. For each of about n starting positions it re-adds k items, which is O(n × k), and when the range can be as large as the whole sequence that becomes O(n²).

The sliding window pattern removes the waste with one observation: consecutive ranges overlap in all but two items. Moving the window one step right means exactly one item enters and one item leaves.

So instead of recomputing, update. Add the entering item, subtract the leaving one. Each item enters the window once and leaves once across the whole pass, so total work is O(n) regardless of how big k is.

That last part is the surprising half. The window can hold 10 items or 10,000 and the cost of the pass does not change, because the cost was never per window in the first place.

O(1) indexing from lesson 2-1 is what makes each update cheap, since temps[i] and temps[i - k] are both single address computations rather than searches.

Recompute against update

Both versions find the best 3-day total. Only the second one avoids re-adding items it has already seen.

temps = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
k = 3

naive_adds = 0
naive_best = 0
for i in range(len(temps) - k + 1):
    total = 0
    for t in temps[i:i + k]:
        total += t
        naive_adds += 1
    naive_best = max(naive_best, total)

window = sum(temps[:k])
best = window
window_ops = k
for i in range(k, len(temps)):
    window += temps[i] - temps[i - k]
    window_ops += 2
    best = max(best, window)

print("best 3-day total (naive):", naive_best, "using", naive_adds, "additions")
print("best 3-day total (window):", best, "using", window_ops, "operations")

Output

best 3-day total (naive): 17 using 24 additions
best 3-day total (window): 17 using 17 operations

The single line window += temps[i] - temps[i - k] is the whole pattern. temps[i] is the item arriving on the right and temps[i - k] is the item falling off the left.

At k = 3 the gap is 24 operations against 17, which is nothing. The interesting part is how each number responds to a larger window: the naive count multiplies by k while the window count does not move at all. At k = 10,000 the naive version would do roughly 10,000 times more work and the sliding version would do the same 17 operations plus the initial sum.

The pass is O(n) because the window total is updated rather than recomputed, so each item is added exactly once when it enters and subtracted exactly once when it leaves.

The trick to seeing this is to count work per item instead of per window. Every item enters the window once and leaves once, two O(1) operations each, so the whole pass costs about 2n operations no matter what k is.

The naive version fails that test. It touches each item once for every window that contains it, which is up to k times, and that repetition is exactly where the O(n × k) comes from.

Counting per item rather than per step is a habit worth keeping, because it is the argument that rescues several algorithms in this course from looking quadratic when they are not.

Windows that grow and shrink

Some questions fix no size k at all. Take the classic: the longest substring with no repeated character, where abcabcbb gives abc with length 3.

Here the window is variable. The right edge grows one character at a time, and whenever the arriving character already sits inside the window, the left edge shrinks until the duplicate is gone.

Two indexes, left and right, mark the window. This is the two-pointer idea from lesson 3-2 with one change: both pointers now move in the same direction rather than toward each other.

Membership has to be O(1), or the check for whether a character is already in the window becomes a scan and the whole saving evaporates. So the window's contents live in a set, the same jump-straight-to-it lookup as the dict in lesson 1-1, with unit 6 covering the machinery.

The cost stays O(n) by the per-item argument again. right moves forward n times, and left only ever moves forward, so it also moves at most n times in total.

That is worth dwelling on, because the inner while loop looks nested and nested loops usually mean quadratic. It cannot run more than n times across the entire pass, since every iteration advances left and left never goes back.

Implementing the variable window

The window grows on the right and shrinks on the left only when it has to.

def longest_unique(s):
    seen = set()
    left = 0
    best = 0
    for right in range(len(s)):
        while s[right] in seen:
            seen.remove(s[left])
            left += 1
        seen.add(s[right])
        best = max(best, right - left + 1)
    return best

for s in ["abcabcbb", "bbbbb", "pwwkew", "abcdef"]:
    print(s, "->", longest_unique(s))

Output

abcabcbb -> 3
bbbbb -> 1
pwwkew -> 3
abcdef -> 6

The shrink step is a while rather than an if, which matters. Several characters may have to leave before the duplicate is gone, since the duplicate could sit anywhere inside the window rather than at its left edge.

Once the while ends, the range from left to right contains no duplicates, so adding s[right] is safe and the length is right - left + 1.

The four cases cover the interesting shapes. abcdef never shrinks and the window grows to the whole string. bbbbb shrinks on every step, since each new b forces the previous one out first, so the window never holds more than one character. pwwkew does both, growing to pw, collapsing at the second w, then growing again to wke.

Each individual item is added into the window total once across the whole pass.

The item at index i is added when the window's right edge first reaches i, and subtracted when the left edge passes it. One add and one subtract, ever, regardless of how many windows happen to contain it.

Summed over all n items that is about 2n operations, which is the entire reason the pattern is O(n) rather than O(n × k).

The naive recompute is the contrast worth holding onto. It adds each item once per window containing it, up to k times, so the same item is summed over and over as the window crawls past it. The sliding window's saving is not a clever formula, it is simply the refusal to repeat that work.