You're given an array and a window of size k sliding left to right. Return the maximum inside each window. The naive scan is O(n·k); the elegant answer is a monotonic deque that runs in O(n). This module breaks down why.
Given nums = [1,3,-1,-3,5,3,6,7] and k = 3, the window starts over the first 3 elements and slides one step at a time. At each position we want the max:
[1 3 -1] → max 3[3 -1 -3] → max 3[-1 -3 5] → max 5[3,3,5,5,6,7]There are n - k + 1windows. Recomputing the max from scratch each time costs O(k) per window — that's the trap.
Keep a double-ended queue of indices whose corresponding values are strictly decreasing from front to back. Two invariants do all the work:
nums[j] ≤ nums[i] and j < i, then j can never be the maximum of any window that also contains i. A newer, bigger element makes the older smaller one useless. So we discard it forever.That single observation is what collapses O(n·k) into O(n): every index enters the deque once and leaves at most once.
For each index ias the window's right edge advances:
deque[0] ≤ i - k), drop it.nums[i], pop it. Maintains the decreasing order.i onto the back.i ≥ k-1 (first full window reached), nums[deque[0]]is this window's max.A heap of (value, index) also works and is a great thing to mention in an interview — but lazy deletion of expired entries pushes it to O(n log n) time and O(n) space. The deque dominates it. Knowing both, and being able to say why the deque wins, is the senior-level answer.
function maxSlidingWindow(nums: number[], k: number): number[] {
const result: number[] = [];
const deque: number[] = []; // stores INDICES; values decreasing front→back
for (let i = 0; i < nums.length; i++) {
// 1 · evict the front if it has slid out of the window
if (deque.length && deque[0] <= i - k) {
deque.shift();
}
// 2 · drain the back of all values ≤ the incoming value
while (deque.length && nums[deque[deque.length - 1]] <= nums[i]) {
deque.pop();
}
// 3 · push the current index
deque.push(i);
// 4 · record the max once the first window is complete
if (i >= k - 1) {
result.push(nums[deque[0]]);
}
}
return result;
}result collects answers; deque holds indices (a plain array used as a deque via shift/pop/push). The values those indices point to stay in decreasing order.i is [i-k+1, i]. If the front index is ≤ i-kit's outside that window, so we shift() it off. Only one element can expire per step, so an if suffices (no loop needed).nums[i]is dominated and gets popped. This is the heart of the trick — it's what guarantees the deque stays decreasing and the front stays the true max.i. It's now the smallest value at the back (everything ≤ it is gone), preserving the invariant.i ≥ k-1. From then on, every step emits exactly one answer: nums[deque[0]].while looks like it could be O(k), but across the whole run each index is pushed once and popped at most once. Total work is bounded by 2n operations ⇒ O(n).>= — keep an increasing deque. Same structure.(value,index) with lazy eviction → O(n log n). The deque is strictly better; naming the tradeoff is the point.k === 1 (result equals input), k === nums.length (single max), empty input. The code handles all three without special-casing.if on line 7 but a whileon line 11?" At most one index expires per advance (front), but many can be dominated at once (back). A favorite gotcha.| "max/min of every sliding window" | monotonic deque of indices |
| need O(1) window extremum | front of the deque = answer |
| newer element ≥ older one | pop the dominated back |
| front index slid out of window | shift it off (deque[0] ≤ i-k) |
const result: number[] = [];
const deque: number[] = []; // indices, values decreasing
for (let i = 0; i < nums.length; i++) {
if (deque.length && deque[0] <= i - k) deque.shift(); // retire old front
while (deque.length && nums[deque.at(-1)!] <= nums[i]) // kick out weak back
deque.pop();
deque.push(i);
if (i >= k - 1) result.push(nums[deque[0]]); // front = max
}
return result;nums[back] ≤ nums[i]?if to evict the front, but line 11 uses a while to drain the back. Why the difference?nums=[7,2,4], k=2, what is the result?