Deque & Sliding-Window Maximum

A deque (pronounced "deck," short for double-ended queue) is a list you can push to and pop from both ends in O(1). That tiny superpower unlocks one of the most loved interview patterns: the sliding window maximum, where we find the largest value in every window of size k as it slides across an array — without rescanning each window from scratch.

Intuition

Imagine a line of people waiting to be "the tallest in the room," ordered tallest-at-the-front. When a taller person arrives, everyone shorter behind them gives up and leaves — they can never be the tallest again while the newcomer is around. And when the person at the front walks out of the room (slides out of the window), the next-tallest is already standing right behind them. That ordered line is our deque, and the front is always the answer for the current window.

The brute-force approach rescans all k elements of every window — that is O(n·k). The deque trick visits each element a constant number of times, giving O(n).

Walk through it

We slide a window of size k = 3 across nums = [1, 3, -1, -3, 5]. The pointers L and R mark the window's edges. The middle strip is the deque, holding indices written as index→value, front on the left. The bottom strip collects the maxes.

Watch two cleanups at each step. First, pop off the back every index whose value is <= the new value — when 3 arrives it evicts 1, because 1 can never out-rank 3 again. Second, pop off the front any index that has slid outside the window. After both cleanups the deque's front is the window's maximum, and once the window is full (R at index k-1) we record it. The maxes come out [3, 3, 5].

The code, line by line

from collections import deque
 
def max_sliding_window(nums, k):
    dq = deque()      # holds indices, values decreasing
    res = []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()              # back: drop smaller
        dq.append(i)              # add new index
        if dq[0] <= i - k:
            dq.popleft()          # front: drop stale
        if i >= k - 1:
            res.append(nums[dq[0]])  # front = max
    return res

• The deque stores indices, not values — we need the index to know when an entry has slid out of the window.
• The while loop (lines 7-8) keeps the deque decreasing: any back entry <= the incoming value is useless, so we pop() it. This is the back end of the deque at work.
• dq.append(i) pushes the new index onto the back.
• dq[0] <= i - k (lines 10-11) checks whether the front index has fallen off the left edge of the window; if so, popleft() removes it from the front.
• Once i >= k - 1 we have a full window, and nums[dq[0]] — the value at the front index — is its maximum.

Complexity

Even though there is a while loop inside the for loop, the total work is O(n): every index is appended exactly once and removed at most once across the whole run, so the pops are amortized constant. The deque never holds more than k indices, so the extra space is O(k).

When to use / pitfalls

Practice