Sliding Windows

A great many questions ask about a stretch of a list: the busiest hour of a day, the longest run of dry days, the shortest piece of a text that holds every letter you need. The items in a stretch are neighbours, and that is what makes these questions easier than they look. When a stretch moves along by one place it is nearly the same stretch as before. Nearly all the work already done can be kept. This module is about keeping it.

Before this, you can: keep two positions on one list and say what is between them; count with a dictionary, and remove a key; count the work a loop does by asking what each item can do.

By the end you will be able to describe a window by its two ends, update a total as a window slides, let a window grow and shrink to keep a rule, decide what a window has to remember, say why the work stays in step with the list, and put the measuring line in the right place.

Before you read on, decide what this prints:

visits = [3, 1, 4, 1, 5, 9]
first = visits[0] + visits[1] + visits[2]
second = first - visits[0] + visits[3]
print(first, second)

8 6

The second total is for positions 1, 2 and 3. It was not worked out by adding three numbers. It was made from the first total by taking off the item that is no longer in the stretch and adding the one that has just come in. Two operations, and it would still be two if the stretch were a thousand items long.

A window on a list

A window is a run of neighbouring items. It is described by two positions, the leftmost item in it and the rightmost, and its length is the number of items from one to the other, both included: right - left + 1.

visits = [3, 1, 4, 1, 5, 9]
k = 3
for left in range(len(visits) - k + 1):
    right = left + k - 1
    print(left, right, visits[left:right + 1])

0 2 [3, 1, 4]
1 3 [1, 4, 1]
2 4 [4, 1, 5]
3 5 [1, 5, 9]

A list of six items has four windows of length 3, because the last one has to start early enough to fit: n − k + 1 windows in general. That + 1, and the + 1 in the length, are where windows go wrong. A window from position 2 to position 4 holds three items, not two.

One leaves, one enters

To find the total of every window, the plain way adds up each one from scratch: k additions for each of n − k + 1 windows. For a day of 1,440 minutes and a window of an hour, that is about 83,000 additions.

Sliding does better. Work out the first window's total the plain way. After that, each window is the one before with one item gone from the left and one new item on the right.

def window_totals(values, k):
    total = 0
    for i in range(k):
        total = total + values[i]
    totals = [total]
    for right in range(k, len(values)):
        total = total - values[right - k] + values[right]
        totals.append(total)
    return totals

print(window_totals([3, 1, 4, 1, 5, 9], 3))

[8, 6, 10, 15]

When the window's right end reaches right, the item that has just dropped out of the left is values[right - k]: exactly k places back. One subtraction and one addition per step, whatever k is. For the day of minutes that is about 2,800 operations where the plain way needed 83,000.

The idea is not special to totals. It works for anything you can update when one item leaves and one enters, without looking at the rest of the window.

A window that grows and shrinks

A window of fixed length answers "which hour was busiest?". Many questions do not fix the length: they ask for the longest stretch that keeps some rule.

Take a hiker who can carry food for a total of 10 kilometres of walking, and a list of the lengths of the stages of a trail. What is the largest number of consecutive stages that fit?

Let the window stretch to the right, one stage at a time. Whenever it holds too much, pull the left end in until it fits again.

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

print(longest_within([4, 2, 5, 1, 1, 3, 6], 10))

4

Follow it. The window takes in 4, then 2: total 6. Then 5: total 11, too much, so the 4 leaves and the total is 7, with the window now holding 2 and 5. Then 1 and 1: totals 8 and 9, and the window is 2, 5, 1, 1, four stages long. Then 3: total 12, so the 2 leaves and the total is 10, which fits: 5, 1, 1, 3, four stages again. Then 6: total 16; the 5 leaves, which makes 11, still too much; then a 1 leaves, and 1, 3 and 6 make 10, which fits. The longest it ever was is 4.

There are three parts, and every growing-and-shrinking window has them in this order. The right end takes one step and the new item is taken in. While the rule is broken, the left item is let go and the left end steps forward. Then the window is valid again, and it is measured.

The window may shrink to nothing. With one stage of 6 and a limit of 5, the 6 is taken in and let go again, which leaves left at 1 while right is 0: one place past the right end is how this loop writes an empty window, and its length, right - left + 1, is 0. The inner loop needs no guard against going further, as long as the stages are positive and the limit is not negative: an empty window has a total of 0, which is then within the limit, so the loop has stopped. With a negative limit it would not stop, and would read past the end of the list. That reasoning depends on the rule. For another rule, check what an empty window does.

What the window has to remember

In the last two sections the window was summed up by one number, its total. That was enough, because the rule was about the total.

For other rules the window has to remember other things, and choosing what is the design. To keep track of how many different kinds of item a window holds, keep a count of each kind in a dictionary. An item that enters adds one to its count. An item that leaves takes one off, and if that brings its count to zero the key is removed, so that the number of keys is always the number of kinds in the window.

counts = {}
for letter in "aab":
    counts[letter] = counts.get(letter, 0) + 1
print(counts, len(counts))

leaving = "a"
counts[leaving] = counts[leaving] - 1
if counts[leaving] == 0:
    del counts[leaving]
print(counts, len(counts))

leaving = "a"
counts[leaving] = counts[leaving] - 1
if counts[leaving] == 0:
    del counts[leaving]
print(counts, len(counts))

{'a': 2, 'b': 1} 2
{'a': 1, 'b': 1} 2
{'b': 1} 1

The first a to leave changes a count and not the number of kinds, because another a is still in the window. The second takes the last one out, and the key goes with it. A key left behind with a count of 0 would make len(counts) say two kinds when there is one. That is the mistake to watch for.

What the window remembers must answer the rule's question at once, and must be something you can update for one item entering and one leaving. A total, a count of each kind, a set when no item may appear twice, a count of how many items break a condition: these cover most windows you will meet.

Counting the work

The growing-and-shrinking loop has a while inside a for. You have seen this before, with the stack of people waiting for someone taller, and the argument is the same.

The right end takes one step per turn of the for: n steps for n items. The left end only ever moves forward, and it never goes further than one place past the right end (the empty window), so over the whole run it takes at most n steps too. One turn of the for may move the left end a long way; then those steps are not available to any later turn. At most 2n moves in all, each with a fixed amount of work.

The plain way, trying every window, looks at about n × n / 2 of them. For a text of a million characters that is the difference between two million steps and five hundred thousand million.

When to measure

The same loop answers two different kinds of question, and the only thing that changes is where the measuring line goes.

For the longest stretch that keeps a rule, as above: take the new item in, shrink until the window is valid, then measure. At that moment the window is the longest valid one ending at right.

For the shortest stretch that reaches something, the logic is turned round. A longer window reaches the target more easily, so you want to shrink it as far as you can while it still reaches. The measuring goes inside the shrinking loop: each time the window still does the job, record its length, and then try it one shorter.

In both, each end only moves forward, and that is what has to be true for the method to be right as well as fast. It is true when making the window longer can only make the rule harder to keep (or the target easier to reach), never the other way. With positive amounts, a longer window always has a larger total. If the amounts could be negative, a longer window might fit when a shorter one did not, and a left end that has moved on would have thrown away the answer. When a window problem gives wrong answers, ask that question first.

In the lab

You will list the windows of a list, update a total as a window slides, and find the busiest hour of a day. You will follow a window as it grows and shrinks, keep count of the kinds of letter in it, and write the longest stretch with no letter twice. You will decide where the measuring line goes for a shortest stretch, and write it, and then the longest stretch with at most k kinds. Four assignments follow: a rearranged word hidden in a text, a window function with two mistakes, sunny days with a few repairs, and one problem that does not tell you there is a window in it.