Sliding window: add one, drop one

A sensor takes one reading a second, 86,400 readings a day. Which hour, 3,600 readings in a row, had the highest total? The obvious way adds up every possible hour: all 82,801 of them, at 3,600 readings each, which is nearly 300 million additions.

But the hour that starts one second later is almost the same hour. It loses its oldest reading and gains one new one; the other 3,599 are shared. Keep one running total and update it with just those two readings, and the whole day takes about 170,000 additions and subtractions.

That is the sliding window. Like two pointers it keeps two indices, but instead of closing in from both ends they move the same way, both to the right, with a running total for the run between them. The same idea handles windows whose size isn't fixed, such as the longest stretch of text with no repeated letter, and it stays O(n).

window

A run of consecutive positions, from a left edge to a right edge. It never skips a position, so it only answers questions about contiguous runs.

window size k

How many values a fixed window holds. With its right edge at i, it covers positions i − k + 1 to i.

slide

Move both edges one place right. One value enters on the right and one leaves on the left; the k − 1 in between stay.

running sum

The total of the values inside the window, kept up to date as the window moves instead of added up again.

variable window

A window whose size changes: the right edge grows it one value at a time, and the left edge shrinks it when a rule says so, such as while the total is over a limit.

This array holds 4, 2, 12, 3, 8, 1 and 9, and the window holds k = 3 values. The visualiser adds up the first window once, then slides it right one place at a time, looking for the 3 consecutive values with the largest sum.

Adding every window up again would cost k additions for each of the n − k + 1 windows: O(n·k), and O(n²) when the window is half as wide as the array. The slide gets the same total with two operations, because the windows before and after it share k − 1 values. Only the value that left and the value that entered differ, so only those two change the total.

Now k = 3 over 6, 1, 4, 9, 2, 3, 8, 5 and 3. At each slide, work out the new total from the old one (add the value entering, subtract the one leaving) and say whether it beats the best so far. A tie doesn't beat it: the first best window found is kept.

The saving grows with k. A slide costs 2 whatever the width, while re-adding a window costs k.

Not every question fixes the size. Say each value is the cost of one day out, and you want the longest run of consecutive days that costs at most 6 in total. The answer might be two days or five, so the window has to grow and shrink:

• The right edge moves one place every step, adding the new cost to the total.
• While the total is over the limit, the left edge moves right, taking costs off, until the window fits again.
• What is left is the longest run ending at the right edge that fits, so compare its length with the best so far.

Dropping the leftmost cost is safe because no cost is negative. A window that is over the limit stays over it however far right it grows, so no run that fits can start at its left edge any more. The code below runs this on the costs 2, 1, 3, 1, 1, 4 and 2 with a limit of 6.

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

costs = [2, 1, 3, 1, 1, 4, 2]
print(longest_run(costs, 6))

The same loop solves many window questions; only the rule and what the window keeps change. For the longest stretch of text with no repeated character, the window keeps a set of the characters inside it, and a repeat entering on the right makes the left edge move until the earlier copy has left. For the shortest run whose total reaches a target, the left edge moves while the total still reaches it, recording the length each time.

• A window is a run of consecutive positions. Keep one running total for it and update it as it moves, instead of adding each window up again.
• A fixed window of k values slides one place at a time: add the value that enters, subtract the one that leaves. That is two operations per slide, so O(n) instead of O(n·k), with O(1) extra space.
• A variable window grows on the right and shrinks from the left when its rule says so, such as while the total is over the limit. Each value enters once and leaves at most once, so it is O(n) too, even with a loop inside a loop.
• Shrinking is only safe when growing can't fix a broken window, as with totals of values that are zero or more. With negative numbers, reach for prefix sums instead.
• Next: the monotonic stack, which keeps its values in order so each is pushed once and popped at most once (open its visualiser); kept in a deque, the same idea gives the largest value in every window in O(n). Practise with Best Single Trade, Longest Stretch Without a Repeat and Longest Run After k Changes, then try the hard one, Smallest Window Holding Every Letter. To try your own values and k, open the sliding window visualiser.