Problem Statement

Sliding Window Maximum

You have a list of numbers and a window of size k. The window is just a frame that shows k numbers in a row. It starts at the far left and slides one step to the right at a time, all the way to the end. For each spot the window lands on, you want the biggest number it can see. Return all those biggest numbers in order, one for each window position.

hardSliding WindowDequeSliding WindowTime: O(n) · Space: O(k)

Signals to notice

maximum in each sliding window of size kthe max must survive as the window slidestrack candidates efficiently

Brute force first

For each window position, scan all k elements for the max. Re-scans overlapping elements redundantly. It is a fair place to begin because it matches the surface of the question, yet it does not capture the deeper structure that makes the problem simpler.

The key insight

Monotonic decreasing deque: maintain a deque of indices where values are in decreasing order. The front is always the current window's maximum. Remove from front when it falls out of the window; remove from back when a larger element arrives. Instead of recomputing the world every time, you preserve just enough context to let the next decision become obvious.

Trace it on `nums=[1,3,-1,-3,5,3,6,7], k=3`

i=0 num=1: dq=[0]; i<2 no output
i=1 num=3: nums[0]=1<3 pop, dq=[1]; no output
i=2 num=-1: dq=[1,2]; i>=2 result=[3] (nums[1])
i=3 num=-3: dq=[1,2,3]; result=[3,3]
i=4 num=5: front idx1 expired popleft, then pop -3 and -1, dq=[4]; result=[3,3,5]
i=5 num=3: dq=[4,5]; result=[3,3,5,5]
i=6 num=6: pop 3 and 5, dq=[6]; result=[3,3,5,5,6]
i=7 num=7: pop 6, dq=[7]; result=[3,3,5,5,6,7] returned

What must stay true

The deque front is always the index of the maximum in the current window. The deque is decreasing — any element smaller than a newer element can never be a future maximum and is discarded. As long as that statement keeps holding, you can trust the steps built on top of it.

Shape of the loop

dq = empty deque of indices; result = []
for i, num in enumerate(nums):
    while dq and dq.front < i-k+1: dq.popleft()   # drop out-of-window
    while dq and nums[dq.back] < num: dq.pop()     # keep decreasing
    dq.append(i)
    if i >= k-1: result.append(nums[dq.front])     # front = window max
return result

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

reaching for a heap and then fighting stale elements that have already left the window. A monotonic deque works better because every index enters once, leaves once, and stays ordered by usefulness. Most mistakes here are not about syntax; they come from losing track of what your state, pointer, or structure is supposed to mean.

Sliding Window Pattern