Deques and Window Extrema

A deque (double-ended queue) supports $O(1)$ push and pop at both the front and the back — strictly more flexible than a stack (one end) or a plain queue (add one end, remove the other). That flexibility is exactly what's needed to answer a question that comes up constantly on streaming numeric data: as a window of the last $k$ values slides forward one step at a time, what's the max (or min) inside it, right now, without rescanning the whole window every step?

The idea: keep the deque monotonic, drop what can never win

Scanning the window from scratch for its max every step costs $O(k)$ per step, $O(nk)$ total — too slow for large windows on a long stream. The fix is a monotonic deque: store indices of candidate maximums, kept in decreasing order of value front-to-back, and maintain two invariants as new elements arrive:

1. Evict from the back any index whose value is smaller than the new element — it can never be the max of any future window that also contains the new element, since the new element is both bigger and more recent.
2. Evict from the front any index that has fallen outside the current window (too old).

After both evictions, the front of the deque is always the index of the current window's maximum — no scan needed, just a peek.

Worked example: sliding window maximum, k=3, array [1, 3, -1, -3, 5, 3, 6, 7]

i	value	evict back (smaller)	deque (indices)	window full?	max
0	1	—	[0]	no	—
1	3	evict 0 (1<3)	[1]	no	—
2	-1	—	[1,2]	yes (0..2)	3
3	-3	—	[1,2,3], evict front 1 (out of window) → [2,3]	yes (1..3)	3
4	5	evict 3,2 (-3<5, -1<5)	[4]	yes (2..4)	5
5	3	—	[4,5]	yes (3..5)	5
6	6	evict 5,4 (3<6, 5<6)	[6]	yes (4..6)	6
7	7	evict 6 (6<7)	[7]	yes (5..7)	7

Result: window maxima are [3, 3, 5, 5, 6, 7] — six windows from eight elements at $k=3$, each answered in $O(1)$ once the deque is maintained.

from collections import deque

def sliding_window_max(nums, k):          # O(n) total, not O(nk)
    dq = deque()                            # stores indices, values decreasing
    result = []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] < x:
            dq.pop()                        # back: evict smaller, now-useless entries
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()                    # front: evict entries that fell out of the window
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

Where it shows up

Interviewers use "sliding window maximum" directly (LeetCode 239) as a test of whether you reach for the naive $O(nk)$ scan or recognize the monotonic-deque pattern; it also underlies "shortest subarray with sum at least K" and several DP-optimization tricks. In quant work, this is the exact structure behind a rolling high/low or a rolling max-drawdown computation over a streaming price series — see Rolling and Expanding Windows for the pandas-level version — and it matters in latency-sensitive settings where recomputing a window's extremum from scratch on every tick would be too slow to keep up with the data.