Challenge: sliding windows

A window is a stretch of values in a row, seen through a frame that slides along the list. Plenty of interview problems ask for the best window: the 7 days in a row with the most sales, the longest stretch of a text with no repeated letter. Working out every window of k values from scratch costs O(n·k), and when the windows can be any length, even growing a window from each start costs O(n²). A sliding window reuses the work: when the window moves, only what enters it and what leaves it changes.

A window of fixed size

The best sum of k values in a row. Instead of sum(values[i - k + 1:i + 1]) at every position, an O(k) sum each time, keep the window's total. When the window moves one place, add the value that enters and subtract the one that leaves:

def best_sum(values, k):
    total = sum(values[:k])
    best = total
    for i in range(k, len(values)):
        total += values[i] - values[i - k]
        best = max(best, total)
    return best


print(best_sum([4, 2, 12, 3, 8, 1, 7], 3))

23

The window that ends at i holds values[i - k + 1] to values[i], so values[i] enters and values[i - k], the value k places back, leaves. Each move is O(1), so the whole function is O(n), whatever k is.

A window that grows and shrinks

Sometimes the size isn't fixed: the longest stretch of days whose spending adds up to at most a budget, limit. Move right along one value at a time and add the new value. While the window breaks the rule, here a total over the limit, take values[left] out and move left on. Then the window from left to right is fine, and its length is a candidate:

def longest_within(values, limit):
    left = 0
    total = 0
    best = 0
    for right in range(len(values)):
        total += values[right]
        while total > limit:
            total -= values[left]
            left += 1
        best = max(best, right - left + 1)
    return best


print(longest_within([2, 1, 3, 2, 6, 1, 1, 1, 2], 6))
print(longest_within([5, -4, 1], 2))  # a negative value: see below

4
2

There's a loop inside a loop, and still the function is O(n): right moves n times, and left only moves forward, so it moves at most n times in all, however the moves are spread. Each value enters the window once and leaves it at most once. The memory is O(1): a few numbers, however long the list is.

Why it's right: the values aren't negative, so adding a value never makes the total smaller. Once the window from left is over the limit, every longer window from left is too, and left can move on for good. With negative values that's no longer true, and the window can miss the answer. That's the second call above: [5, -4, 1] adds up to 2, within the limit, so the answer is 3. But the window drops the 5 as soon as the total goes over 2, before the -4 can bring it back down, and it returns 2. For a stretch that adds up to exactly k, negative values are no problem: use the prefix sums and the dict of the last step. For the biggest sum of a stretch of any length, use the last step's biggest_stretch.

The window's state isn't always a total. For a stretch of text with no repeated character, the state is which characters are in the window, kept in a set or in a dict of where each character was last seen. When the new character is already in the window, left moves past its earlier copy. The dict has one entry for each different character of the text: O(n) memory at most, and at most 26 entries for a text of lowercase letters.

Three jobs in one loop

Look again at the loop of longest_within. Each round does three jobs, and most windows of changing size do the same three:

• Grow: the for loop hands right the next value, and total += values[right] takes it in.
• Repair: while total > limit, the window isn't allowed, so it gives back values[left] and left moves on. Since left never moves back, all the repairs together cost O(n).
• Measure: now the window from left to right is allowed, and right - left + 1 may be the best so far.

Only the state and the rule change from problem to problem. When the question is the shortest window that reaches a target, repairing and measuring trade places: while the window still reaches the target, measure it first, then give back values[left] to see whether a shorter window reaches it too.