Monotonic deque in Python

Why it matters

A common programming task is to look at a stretch of data and report one number about it. "What is the highest temperature in each group of three days?" is one example. "What is the largest price in the last ten minutes?" is another. The stretch slides forward one item at a time, and you need an answer for every position.

The simple way to do this repeats a lot of work. A monotonic deque is a small data structure that avoids the repeated work. It keeps the answer ready as the stretch moves. In this lesson you will build it for the largest value in a window, and then use the same idea for two harder problems.

The lesson assumes you know what a list is and what a for loop does. It uses collections.deque, a double-ended queue. A deque lets you add and remove items at both ends in O(1) time, which means the same small cost however long the deque is.

The problem: the biggest value in each window

Take the list [1, 3, -1, -3, 5, 3, 6, 7]. Choose a window size k = 3. A window is a block of k values next to each other in the list. The first window is [1, 3, -1]. The second window is [3, -1, -3]. Each window moves one step to the right.

For each window, the task is to write down its largest value. The output is [3, 3, 5, 5, 6, 7], one number for each of the six windows.

Check the first answer by eye. The first window is 1, 3, -1. The largest is 3. The second window is 3, -1, -3. The largest is 3 again. The third window is -1, -3, 5. The largest is 5. You can see the pattern: each window shares most of its values with the window before it. Only one value leaves on the left, and one value enters on the right.

The slow way

The simple method checks every value in every window. Here is the code.

def naive_window_max(nums, k):
    result = []
    for start in range(len(nums) - k + 1):
        best = nums[start]
        for j in range(start + 1, start + k):
            best = max(best, nums[j])
        result.append(best)
    return result

This code is correct. Its cost is the problem. For each window it looks at k values, and there are about n windows, where n is the length of the list. The total work is about n * k steps. When n is one million and k is ten thousand, that is about ten billion steps. A computer runs maybe a billion simple steps per second, so the program would take many seconds.

Big-O notation is a short way to say how work grows as the input grows. O(n) means the work grows in a straight line with n: double the input, and the work doubles. O(n * k) means the work also depends on the window size. The goal of this lesson is an O(n) method that does not care about k at all.

The idea: a deque that stays sorted

The naive method throws away its work at every step. The monotonic deque keeps just enough information to answer the next window quickly.

What a deque is

A deque (pronounced "deck") is a line of items where you can add or remove from either end. In Python you create one like this:

from collections import deque
 
dq = deque()

The methods you need are these.

• append(x) adds x at the back.
• pop() removes and returns the item at the back.
• popleft() removes and returns the item at the front.
• dq[0] and dq[-1] look at the front and the back without removing anything.

Two details matter later. The methods pop and popleft raise IndexError on an empty deque, so check if dq: before you call them. And reading dq[0] on an empty deque also raises IndexError.

What goes into the deque

The deque holds indexes, which are the positions in the list, not the values. Storing positions lets you check whether an item has left the window. The values are found by looking up nums[index].

The deque is kept in a special order. The values, read from front to back, go down. In other words, the front holds the largest value in the deque. This order is what makes the monotonic deque work. The word "monotonic" means "always going one way", and here the values always go down from front to back.

The two rules

Each time a new index i arrives, the code follows two rules.

1. Remove from the back any index whose value is less than or equal to nums[i]. Those values can never be the answer again. The new value is bigger, and it stays in the window longer, because it is further right. So the old value is useless.
2. Add i at the back.

There is one more step. The front index may have left the window. If so, remove it from the front. The window now covers positions i - k + 1 through i, so any index at or below i - k is out of date.

After these steps, the front of the deque holds the largest value in the current window. Once the first full window exists, that value is the answer.

A worked example, one step at a time

Use the small list [4, 2, 12, 11, -5] and window size k = 2. The program below prints the deque after each step.

The output of the trace is:

i=0 value=4 deque(indices)=[0] values=[4]
i=1 value=2 deque(indices)=[0, 1] values=[4, 2]
i=2 value=12 deque(indices)=[2] values=[12]
i=3 value=11 deque(indices)=[2, 3] values=[12, 11]
i=4 value=-5 deque(indices)=[3, 4] values=[11, -5]
Result: [4, 12, 12, 11]

The same steps in a table, with the window that each row covers:

Look at row 2 in detail. The value 12 arrives. The window is now positions 1 and 2, so index 0 has left it. The front rule removes index 0 first. Then index 1 (value 2) is at most 12, so the back rule removes it too. The deque is empty, and index 2 goes in. The deque is [2], and the front value 12 is the answer for the window [2, 12].

Look at row 3. The value 11 arrives. The back holds index 2 with value 12. Since 12 is more than 11, nothing is removed. Index 3 goes at the back, and the deque is [2, 3], with values 12, 11 going down. The front is still 12, which is the answer for the window [12, 11].

Look at row 4. The value -5 arrives. The front index 2 is now out of the window, because the window is positions 3 and 4. It is removed. The new front is index 3 with value 11. The answer for the window [11, -5] is 11.

Why the total cost is O(n)

A reader often asks why a loop with a while inside is still fast. The answer is that each index is added to the deque once and removed at most once. The while loop removes items from the back, but every removal is an index that will never be added again. Over the whole run, the number of removals cannot be more than the number of additions.

Count the work. There are n additions, and at most n removals from the back and n removals from the front. Each step has a fixed small cost. The total is about 3n steps, which is O(n). This kind of reasoning, where one expensive step is paid for by many cheap ones, is called amortized cost. Amortized means "spread out over all the steps".

The full method

Here is the method you can keep and reuse. It is the same code as the trace, without the printing.

The output is:

[3, 3, 5, 5, 6, 7]

This matches the naive method. A scratch test compared the two methods on 3,000 random lists, with random window sizes, and found no mismatch.

Worked example two: the sliding window minimum

The same structure finds the smallest value in each window. The only change is the direction of the comparison. The deque now keeps values that go up from front to back, so the front is the smallest.

The output is:

[-1, -3, -3, -3, 3, 3]

Inside the loop, only one character changed: <= became >= in the while line. Check the first two windows by eye. [1, 3, -1] has minimum -1. [3, -1, -3] has minimum -3.

This example shows the general rule. A monotonic deque is a sorted line kept by removing from the back. Choosing <= makes the front the maximum. Choosing >= makes the front the minimum. The rest of the code stays the same.

Worked example three: the longest stretch with a small spread

The third example is harder, and you can skim it on a first read. It uses two deques at once.

The question is this. Given a list and a limit, find the longest stretch of neighbouring values where the largest value minus the smallest value is at most the limit. A stretch is a block of values next to each other, like a window, but its length is not fixed. It grows and shrinks.

Take [8, 2, 4, 7] with limit 4. The stretch [2, 4] has spread 2, which is fine, and length 2. The stretch [2, 4, 7] has spread 5, which is too big. The longest valid stretch has length 2.

The method keeps two deques. One keeps the maximum of the current stretch, the same as before. The other keeps the minimum, using the >= version. A second index, left, marks where the stretch starts. The stretch runs from left to right.

The output is:

2
4
3

The outer loop moves right one step at a time. The inner while moves left forward only when the spread is too big. Each time left moves past an index, the front of a deque may be out of range, so the code removes it. Both left and right only move forward, so the whole run is still O(n).

In the second example, the input is [10, 1, 2, 4, 7, 2] with limit 5, and the answer is 4, for the stretch [2, 4, 7, 2]. Its spread is 7 - 2 = 5, which is allowed. The stretch [1, 2, 4, 7, 2] is one longer, but its spread is 6, which is too big. In the third, the input is [4, 2, 2, 2, 4, 4, 2, 2] with limit 0, and the answer is 3, for the stretch [2, 2, 2], where every value is the same.

A slow check that tries every stretch gives the same answers on these inputs, and on random lists in the scratch test. The slow check is useful for testing a fast method, because it is easy to trust.

Common mistakes

Storing values instead of indexes. A beginner often appends nums[i] to the deque. Then the code cannot tell whether the front value is still inside the window. Two equal values in different positions look the same. Store the index, and read the value with nums[index] when you need it.

Checking the wrong end. The expired check must look at the front, with dq[0] and popleft. The removal of smaller values must look at the back, with dq[-1] and pop. Swapping these two gives wrong answers that can look right on short tests.

Forgetting the empty check. dq[0] and popleft raise IndexError on an empty deque. This program calls each one on an empty deque:

The output is:

caught: pop from an empty deque
caught: deque index out of range

Always write if dq: before you read the front or pop.

Expecting None to be refused. Python's deque accepts None as an item. Java's ArrayDeque refuses it, so the rule from the other language does not apply here. Window code never needs to store None, and a None in the deque would break the comparisons, so check where a value came from.

Asking for a window bigger than the list. The result list has size n - k + 1. If k is bigger than n, the size is negative. Python does not stop with an error here, because [0] * -1 is an empty list. The function then returns [] without any warning. For example, window_max([1, 2], 5) returns [].

Check that k is at most n before you call the function, and raise an error if it is not.

Using the wrong comparison for the goal. Use <= in window_max and >= in window_min. Mixing them gives a deque that does not stay sorted in the right direction, so the front is not the answer. Decide first whether you want the largest or the smallest, then pick the comparison.

Practice

Exercise 1. Use the method by hand, without running code. Find the output of window_max on [1, 3, -1, -3, 5] with k = 3.

Show the answer: the three windows are [1, 3, -1], [3, -1, -3] and [-1, -3, 5]. Their maximums are 3, 3 and 5. The output is [3, 3, 5].

Exercise 2. The function window_max answers for windows of size k. Change it so that it returns the sum of each window instead of the maximum. Explain why this change does not work with a monotonic deque.

Show the answer: a sum cannot be kept in the deque. A deque keeps the values that could be the answer later, and a value that is smaller can still matter for a sum. The deque trick depends on the fact that a smaller value can never beat a larger one that stays in the window longer. That fact is false for sums. A sum needs a different method, such as a running total with a subtraction for the value that leaves.

Exercise 3. Why does the code store indexes and not values in the deque? Give one example where storing values breaks the expired check.

Show the answer: the expired check asks whether the front item is still inside the window. An index can be compared with i - k to answer that. A value cannot. Take [5, 1, 5] with k = 2. The value 5 appears at index 0 and at index 2. If the deque held values, you could not tell which 5 is in the window. Index 0 is out of the window at step 2, but a value-only deque cannot say so.

Exercise 4. What does window_max return when k = 1? What does it return when k equals the list length?

Show the answer: when k = 1, every window is one value, so the output is the list itself. Running the code on [1, 3, -1, -3, 5, 3, 6, 7] with k = 1 gives [1, 3, -1, -3, 5, 3, 6, 7]. When k equals the list length, there is only one window, which holds all the values. For the same list the output is [7].

Exercise 5. Find the answer of longest_within_limit for [7, 7, 7, 8, 7] with limit 0.

Show the answer: the spread must be 0, so every value in the stretch must be the same. The longest run of equal values is 7, 7, 7, with length 3. The answer is 3.

Summary

• A window is a block of k values that moves one step at a time, and the naive method costs about n * k steps.
• A monotonic deque holds indexes in an order where the values go one way, so the front holds the answer.
• Each new index removes smaller values from the back, adds itself at the back, and removes an expired index from the front.
• Each index enters and leaves the deque at most once, so the total cost is O(n).
• Changing <= to >= turns a maximum method into a minimum method.
• The same idea works with two deques for a stretch whose length is not fixed.