Sliding Window Maximum
Return the maximum of every window of size k as it slides across the array.
- 1 <= nums.length <= 10⁵
- -10⁴ <= nums[i] <= 10⁴
- 1 <= k <= nums.length
Intuition
Sliding window maximum asks for the largest value in every window of size k as it slides across the array. Recomputing the maximum per window is O(n·k), and a heap improves it to O(n log k) — but there is an O(n) solution, and the idea behind it is worth internalising.
Ask which elements inside the current window can ever be a future maximum. Suppose element x sits somewhere in the window and a later element y > x arrives. Every window that still contains x from now on must also contain y, because y is to its right and windows only move forward. So x can never be the maximum again:
- An element with a larger element to its right is permanently useless and can be discarded.
Maintaining that rule leaves a sequence of decreasing values — the current maximum at the front, then the best candidate if that expires, and so on. New elements pop everything smaller off the back before joining.
The structure has to support removal at both ends: from the back to discard dominated elements, and from the front to expire elements that have slid out of the window. That is exactly a deque, and both ends are O(1).
Store indices rather than values, since expiring from the front requires knowing whether an element's position has fallen out of the window — information a bare value does not carry.
A monotonic deque is for when you need the max or min of a moving window and a heap's lazy deletion feels clumsy. The insight is that if a newer element is bigger than an older one, the older one can never be the answer again — it's dominated for the rest of time. Discard it permanently, and the deque stays sorted so the front is always the answer. Each index is pushed and popped once, giving O(n).
Approach
Before reading on: price up what the direct approach costs here, then ask what ordering you can maintain so the answer is always at one end. Aim for O(n) time and O(k) space.
Work out which elements can be discarded
If a larger element appears to the right of x, then every future window containing x also contains that larger element. x can never be a maximum again, so it can be dropped permanently rather than kept and compared.
Keep a deque of indices, not values
The deque holds indices whose values decrease from front to back. Indices are required because expiring the front means checking whether a position has left the window, which a value alone cannot tell you.
Pop dominated elements from the back
Before pushing index i, pop from the back while the value there is less than or equal to nums[i]. Those elements are dominated by the newcomer. This is a while loop — one large value can evict many candidates at once.
Expire the front when it leaves the window
If the front index equals i - k, it has slid out of the window; pop it from the front. Only one element can expire per step, so a single if suffices here rather than a loop.
Emit once the first window is complete
From i >= k - 1 onward, the value at the front index is the maximum of the current window. Append it to the results — one output per position from that point on.
Cost across the whole array
Each index is pushed exactly once and popped at most once, so the total work is O(n) despite the inner while loop. Space is O(k), since the deque never holds more than one window's worth of indices.
Solution & live demo
Common pitfalls
Storing values instead of indices
while dq and dq[-1] <= x:
dq.pop()
dq.append(x)while dq and nums[dq[-1]] <= x:
dq.pop()
dq.append(i)Expiry is positional — you need to know when the front entered to know when it slides out of the window. With bare values you can't tell an old 5 from a fresh one. Store indices and dereference through nums for comparisons.
Popping with < and leaving duplicates
while dq and nums[dq[-1]] < x:
dq.pop()while dq and nums[dq[-1]] <= x:
dq.pop()Equal values pile up in the deque, and although the maximum stays correct, the stale copies survive past their expiry and bloat the structure. The newer index dominates an equal older one in every future window, so evict it.
Emitting before the first window is full
res.append(nums[dq[0]])
if i >= k - 1:
res.append(nums[dq[0]])The first complete window only exists once you've consumed k elements. Emitting from index 0 produces k - 1 extra leading answers computed over partial windows.
Edge cases
Deque holds only the current index; output = input.
Nothing pops from the back; front expiry does all the work.