Sliding Window Maximum with a Monotonic Deque

A window of fixed width k slides across an array one position at a time. Report the maximum inside it at every position. For [1, 3, -1, -3, 5, 3, 6, 7] with k = 3 the answer is [3, 3, 5, 5, 6, 7].

Rescanning each window is O(n·k) and correct. A max-heap gets that to O(n log k). Neither is the best available: the problem has a genuine O(n) solution, and the structure behind it — a deque kept in decreasing order — is worth knowing because the same trick solves a family of window problems.

Why the obvious approaches fall short

Recomputing the maximum for each of the n − k + 1 windows costs O(k) each time, so O(n·k) overall. With n = 100,000 and k = 50,000 that is billions of comparisons, and it repeats almost all of its work: consecutive windows share k − 1 elements.

A max-heap improves it. Push each element, and when the top of the heap has fallen out of the window, discard it. That is O(n log k). It is a reasonable answer and it will pass many judges. But it still pays a logarithmic price per element for information the array's own order already gives away.

The observation that gives O(n)

Consider two positions i and j with i < j and nums[i] <= nums[j].

The element at i can never be the answer again. Any window that still contains i also contains j, because j is further right and windows only move right. And j is at least as large. So i is dominated permanently, and can be thrown away the moment j arrives.

Apply that rule relentlessly and what survives is a sequence of indices whose values strictly decrease from front to back. The front is the largest, so it is the window's maximum — and the rest are the candidates waiting to inherit the title once the front expires.

The two removal rules

The deque needs exactly two kinds of removal, and confusing them is the usual source of bugs:

1. From the back — dominance. Before pushing index i, pop while the value at the back is <= nums[i]. Those candidates are permanently beaten.
2. From the front — expiry. If the front index has fallen outside the window, pop it. It is still the largest of what remains in the deque, but it is no longer inside the window.

Walking through an example

nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3. The deque column shows values for readability; the code holds their indices.

The code

from collections import deque


def max_sliding_window(nums, k):
    window = deque()   # indices, values strictly decreasing front to back
    out = []

    for i, n in enumerate(nums):
        # Dominance: anything smaller at the back is finished.
        while window and nums[window[-1]] <= n:
            window.pop()
        window.append(i)

        # Expiry: the front may have slid out of range.
        if window[0] <= i - k:
            window.popleft()

        # Only emit once the first full window exists.
        if i >= k - 1:
            out.append(nums[window[0]])

    return out

Why the inner loop does not make it quadratic

There is a while loop inside a for loop, which looks like O(n·k). It is not, and the argument is worth internalising because it recurs across amortised analyses.

Count the pushes. Each index is pushed exactly once, during its own iteration — n pushes in total. Each pop removes an index that was already pushed, so there can be at most n pops across the entire run, no matter how they cluster. One iteration may pop many; it can only do so because earlier iterations pushed them and did not pop.

Total work is therefore bounded by 2n deque operations plus n comparisons: O(n) time, and O(k) space because the deque never holds more than one window's worth of indices.

The mistakes that actually happen

• Popping the front before checking dominance. Expiry must be tested against the current index after the push, or a front that is still valid gets discarded.
• Using < rather than <= in the dominance test. With equal values the deque keeps duplicates; the answer is still correct but the deque grows larger than it needs to. Either is defensible, but be deliberate about it.
• Emitting before the first full window. Nothing should be output until i reaches k − 1.
• Storing values instead of indices, which makes expiry impossible to detect.
• In JavaScript, shift() on a plain array is O(n) in the worst case. It is fine at these sizes, but a real deque is the honest structure.