Sliding Window Maximum With a Deque, Step by Step

A sliding window sum is easy: add the value coming in, subtract the value going out. A sliding window maximum is not, because a maximum cannot be un-added. When the largest value slides out on the left, you need to know the runner-up — and the runner-up after that. The deque solution is the data structure that keeps exactly that list, and nothing else.

The problem it solves

Given an array and a window size k, report the largest value in every contiguous window of length k. Rolling peak load over the last five minutes, the best price in the last seven days, the loudest sample in a moving audio frame.

The brute force takes max() of every window: O(n · k). A heap improves that to O(n log n), but a heap has no cheap way to remove an arbitrary element, so you end up leaving expired values in it and discarding them lazily when they surface at the top. It works; it is also more machinery than the problem needs.

The intuition

One observation does all the work:

If a value arrives that is at least as large as an older value in the window, the older one can never be the maximum again.

The newer value is bigger, and it will stay in the window longer, because it arrived later. Every future window that still contains the old value also contains the new one. The old value is dominated for the rest of its life, so throw it away now.

Apply that rule on every arrival and the survivors form a strictly useful list: each one is smaller than everything ahead of it but newer, so each is the maximum-in-waiting for the moment its seniors expire. That list is in decreasing order automatically, and it changes at both ends, which is why the container is a double-ended queue:

• The back is where new values fight their way in, popping everything they dominate.
• The front is the current maximum, and it leaves only when it expires out of the window.

Watch it run

Follow the deque row as the window moves. A large arrival clears the back in one go; the front changes only when its index falls out on the left. Notice that the deque never holds more than it needs to — often just one or two values.

The code

The deque stores indexes, not values, because the expiry test needs positions. The trace prints the values those indexes point at, so you can check each step by hand.

from collections import deque

def window_max(nums, k, trace=False):
    dq, out = deque(), []              # indexes; their values decrease
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()                   # dominated: older and no larger
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()               # expired: slid out on the left
        if i >= k - 1:
            out.append(nums[dq[0]])    # the front is the answer
        if trace:
            print(i, x, [nums[j] for j in dq])
    return out

print(window_max([1, 3, -1, -3, 5, 3, 6, 7], 3, trace=True))
# 0 1 [1]
# 1 3 [3]            3 dominates 1
# 2 -1 [3, -1]
# 3 -3 [3, -1, -3]   three survivors, one per future window
# 4 5 [5]            5 clears the whole deque
# 5 3 [5, 3]
# 6 6 [6]
# 7 7 [7]
# [3, 3, 5, 5, 6, 7]

Step 3 is the interesting one. The deque holds three values because each is a legitimate answer for some future window: 3 now, -1 once 3 expires, -3 once -1 expires. Then 5 arrives and makes all three irrelevant in a single step.

The complexity

Time: O(n). The inner while loop does not make it quadratic, for the same accounting reason as the monotonic stack: every index is appended exactly once and removed at most once, from one end or the other. Total deque operations are at most 2n, however they are distributed.

The two extremes confirm it. Instrumenting the function on 100,000 values with k = 1000:

• Strictly descending input — nothing is ever dominated, so every removal is an expiry from the front: 100,000 appends plus 99,000 front pops.
• Strictly ascending input — every arrival dominates its predecessor: 100,000 appends plus 99,999 back pops.

Both stay under 2n.

Space: O(k). An expired index is removed as soon as it leaves the window, so between steps the deque holds at most k indexes — and reaches that only on descending runs.

Where it goes wrong

• Storing values instead of indexes. With values you cannot tell whether the front has expired, and with duplicates you cannot tell which copy expired.
• Reading the front before the expiry check. The expiry must happen first, or you report a maximum from a window that has already moved on.
• if versus while for the front. Because the index advances by exactly one per step, at most one index can expire per step, so if is correct. A variable-size window, where the left edge can jump, needs while.
• <= versus < on the back. Both give correct answers. <= evicts equal values too, keeping only the newest copy, which is the one that will live longest — so the deque stays smaller. With <, duplicates pile up and still pop correctly from the front.
• Forgetting the warm-up. No output until i >= k - 1; the first k - 1 steps only build the deque.
• Edge sizes. k = 1 returns the array itself; k = n returns one value; k larger than the array usually means an empty answer or an error — ask which the interviewer wants.

For the sliding window minimum, flip the comparison to >=. The same deque shape also powers harder problems — the shortest subarray with a sum of at least K, or dynamic programming that needs the best of the last k states — anywhere "best of a moving range" appears.

How to say it in an interview

"The brute force recomputes the maximum per window, O(n · k). Instead I keep a deque of indexes whose values are decreasing. When a new value arrives, anything smaller at the back is dominated — it is older and smaller, so it can never be a maximum again — and I pop it. The front leaves only when its index falls out of the window, and the front is always the current maximum. Each index enters and leaves once, so it is O(n) time and O(k) space."

The word to use is dominated. It explains why discarding is safe in one sentence, and that sentence is what the interviewer is listening for.