Deques and the sliding window maximum

A deque allows push and pop at both ends in O(1). That freedom powers one of the most elegant results in this course: the maximum of every window of size k, in O(n).

The naive cost

Recomputing the maximum per window is O(n × k). A heap improves it to O(n log k). A monotonic deque does it in O(n).

The idea

Hold indices in the deque, with their values in decreasing order. Then:

• the front is always the maximum of the current window;
• anything smaller than an incoming value can never be a maximum again, so drop it;
• anything that has slid out of the window is evicted from the front.

function slidingWindowMax(items, k) {
  const deque = [];        // indices, values decreasing front → back
  const out = [];

  for (let i = 0; i < items.length; i++) {
    // 1. Drop indices that have left the window.
    if (deque.length && deque[0] <= i - k) deque.shift();

    // 2. Drop values smaller than the newcomer: they are now irrelevant.
    while (deque.length && items[deque.at(-1)] <= items[i]) deque.pop();

    deque.push(i);

    // 3. Once the first full window exists, the front is its maximum.
    if (i >= k - 1) out.push(items[deque[0]]);
  }

  return out;
}

Every index enters and leaves the deque once: O(n) total, O(k) space.

The correctness argument in one sentence: if a later element is at least as large as an earlier one still in the deque, the earlier one can never be the maximum of any window containing both — so discarding it loses nothing.

Why the deque, specifically

Step 1 removes from the front, step 2 from the back. A stack cannot do the first and a queue cannot do the second — the problem genuinely needs both ends.

(The shift() above is O(k) in the worst case on a JavaScript array; for large k, use a head index or a linked deque. Worth saying out loud in an interview.)

Related uses

• Shortest subarray with sum at least k, with negative numbers — deque over prefix sums.
• 0-1 BFS, where zero-weight edges push to the front and weight-one edges to the back, replacing Dijkstra's heap with a deque.
• Work stealing schedulers, where a worker takes from its own front and thieves take from the back.