Sliding Windows

Many questions are about stretches of data: the busiest hour, the longest streak, the shortest stretch that adds up to enough. Checking every stretch means checking every start and every end, which is O(n²) stretches. A sliding window checks far fewer by noticing that neighbouring stretches share almost everything.

The worked examples here are a moving average, a spending streak and an anagram search. The lab uses the same ideas on letters and visits.

What a window is

A window is a stretch of positions from left to right, both included. Its length is right - left + 1, and a window of k items that starts at left ends at right = left + k - 1. Deciding once how the bounds are written, and sticking to it, removes most off-by-one bugs.

When the window moves one step, only its edges change: one item enters at the right and one leaves at the left. Everything in the middle is still there. The whole technique is:

Keep what you know about the middle; update it only at the edges.

Fixed windows: the moving average

Average temperature over every three consecutive days. The obvious code adds up each window from scratch:

def averages_slow(temps, k):
    return [sum(temps[i:i + k]) / k for i in range(len(temps) - k + 1)]

That is k additions per window, O(n × k) in total. Instead, keep a running total and adjust it at the edges:

def averages(temps, k):
    if len(temps) < k:
        return []
    total = sum(temps[:k])
    result = [total / k]
    for right in range(k, len(temps)):
        total += temps[right] - temps[right - k]   # one enters, one leaves
        result.append(total / k)
    return result

temps = [20, 22, 21, 25, 30, 28]
assert averages(temps, 3) == averages_slow(temps, 3) == [21.0, 22.666666666666668, 25.333333333333332, 27.666666666666668]

Each step is two operations, so the whole scan is O(n) whatever k is. The number of windows is len(temps) - k + 1 — worth counting on paper before you write the loop.

Variable windows: grow, then shrink

Now the window's size is the answer. Every day's spending is positive; what is the longest streak of days that stays within a budget?

def longest_within(spend, budget):
    best = 0
    total = 0
    left = 0
    for right in range(len(spend)):
        total += spend[right]                 # grow on the right
        while total > budget:                 # shrink on the left until legal again
            total -= spend[left]
            left += 1
        best = max(best, right - left + 1)
    return best

assert longest_within([3, 1, 2, 7, 1, 1, 1], 6) == 3
assert longest_within([9, 9], 5) == 0

right moves forward one step per loop. left moves forward only when the window breaks its rule, and it may need to move several times in one step — which is why the shrink is a while, not an if.

The invariant:

After each step, the window spend[left..right] is within budget, total is its sum, and neither pointer has ever moved backwards.

That last clause is what makes the cost O(n) even though there is a loop inside a loop: left crosses the list at most once in total, so the inner while runs at most n times over the whole scan, not n times per step.

It also depends on the values being positive. With positive values, making a window longer only raises its total and making it shorter only lowers it, so moving left forward can never skip a better answer. With negative values that is no longer true, and the sliding window gives wrong answers; problems like that need a different tool, such as prefix sums.

Windows that remember contents

Sometimes the rule is about what is in the window, not a total. Does a text contain some rearrangement of a word — for example, is there an anagram of "ab" in "eidbaooo"? A window of len(word) letters slides across the text, and a dictionary counts the letters inside it:

def contains_anagram(text, word):
    k = len(word)
    need = {}
    for ch in word:
        need[ch] = need.get(ch, 0) + 1
    window = {}
    for right, ch in enumerate(text):
        window[ch] = window.get(ch, 0) + 1            # letter enters
        if right >= k:
            leaving = text[right - k]
            window[leaving] -= 1                       # letter leaves
            if window[leaving] == 0:
                del window[leaving]                    # keep only letters present
        if window == need:
            return True
    return False

assert contains_anagram("eidbaooo", "ab") is True
assert contains_anagram("eidboaoo", "ab") is False

The del line matters. A key whose count has fallen to zero still exists, so without it window would contain {"e": 0, ...} and never equal need. The same slip breaks any window that uses len(counts) to mean "how many different letters are inside": zero counts must be removed.

A set is enough when a letter can appear at most once in the window (the lab's "no repeated letter" exercise). When a letter can appear several times, the window needs counts.

What it costs

Where it goes wrong

• if where while is needed. One step can make the window illegal by more than one item.
• Zero counts left in the dictionary. The window "contains" letters it does not.
• Off-by-one bounds. Decide that both ends are included, and compute lengths as right - left + 1.
• Negative values in a sum window. The grow-and-shrink logic assumes adding never lowers the total.
• Right answer, wrong windows. A loop can return the correct number while some window along the way broke the rule. The lab's frames make every window visible, and its checks read them.

In the lab

The lab slides a fixed window across a word frame by frame, keeps a running total for the best three days in a row, finds the longest stretch without a repeated letter using a set, and allows up to k kinds of letter using a count dictionary, with checks that inspect every window you drew. The mastery challenge moves the idea to numbers and names no technique: you choose the plan and explain why it needs every value to be positive.