Deques and the sliding-window maximum

A deque, short for double-ended queue, lets you add and remove items at both ends, front and back, in O(1). Deques generalise both stacks and queues: use one end only and you have a stack, add at one end and remove at the other and you have a queue. Their best-known use is the sliding-window maximum: the largest value in every run of k consecutive values of a list. Rescanning each window costs O(nk); a deque that keeps only the values that can still win answers every window in O(n) for the whole list. This lesson states an original version of the problem, measures the brute force, and shows what to notice before writing the fast version.

The problem: the hottest day of every week

A weather station keeps the highest temperature of each of n days. For every window of k consecutive days, report the highest temperature in that window: n − k + 1 answers, from the window that starts on day 0 to the one that ends on the last day.

• Input: n whole numbers, temps[0] to temps[n - 1], and a window size k, with 1 ≤ k ≤ n ≤ 10⁶ and −60 ≤ temps[i] ≤ 60.
• Output: n − k + 1 numbers, the maxima of the windows 0..k-1, 1..k, and so on.
• Time limit: about two seconds.

For [30, 32, 31, 29, 35, 34, 28, 27] with k = 3 the answer is [32, 32, 35, 35, 35, 34]. A window of a single day just repeats the log, and a window as long as the log gives one number, the highest temperature overall.

The brute force: rescan every window

def window_max_brute(values, k):
    """The maximum of every window of k consecutive values, rescanning each window. Returns them and the comparisons."""
    out, comparisons = [], 0
    for start in range(len(values) - k + 1):
        best = values[start]
        for x in values[start + 1 : start + k]:
            comparisons += 1
            best = max(best, x)
        out.append(best)
    return out, comparisons


temps = [30, 32, 31, 29, 35, 34, 28, 27]
print("k = 3:", window_max_brute(temps, 3)[0])
print("k = 1:", window_max_brute(temps, 1)[0])
print("k = 8:", window_max_brute(temps, 8)[0])
print()
print(f"{'n':>6} {'k':>6} {'comparisons':>12} {'(n - k + 1)(k - 1)':>20}")
for n, k in [(2_000, 10), (2_000, 500), (2_000, 1_000), (2_000, 1_990)]:
    _, comparisons = window_max_brute(list(range(n)), k)
    print(f"{n:>6,} {k:>6,} {comparisons:>12,} {(n - k + 1) * (k - 1):>20,}")

k = 3: [32, 32, 35, 35, 35, 34]
k = 1: [30, 32, 31, 29, 35, 34, 28, 27]
k = 8: [35]

     n      k  comparisons   (n - k + 1)(k - 1)
 2,000     10       17,919               17,919
 2,000    500      748,999              748,999
 2,000  1,000      999,999              999,999
 2,000  1,990       21,879               21,879

Each window costs k − 1 comparisons, so the whole log costs (n − k + 1)(k − 1), as the counts confirm. That is largest when k is about n/2, about n²/4: at n = 10⁶ and k = 5 × 10⁵, some 2.5 × 10¹¹ comparisons, hours of work in Python and minutes even in compiled code. A heap of the window’s values does better, O(n log k), but it still pays a logarithm for every day.

What to notice

A temperature that is older than another one in the window, and not higher, can never be the maximum of any later window: the newer one stays in every later window the older one is in, and is at least as hot. Throw such readings away, and the ones that remain fall from oldest to newest. New readings join at the newest end, and readings that leave the window leave from the oldest end, which is the shape of a deque. Deques are made for exactly this, and they are how the sliding-window maximum comes down to a single pass.

The deque of candidates, step by step Pro: opens with a Pro, Premium or Ultimate pass