Sliding Window Maximum: given an array and window size k, return the max of each window. The deque solution is the optimal O(n) approach and a classic.

Why brute force and heap aren't ideal

• Brute force — recompute the max of each window: O(n·k).
• Heap — a max-heap of window elements: O(n log k), but you need lazy deletion of out-of-window elements.
• Deque — O(n). The trick.

The deque approach

Maintain a double-ended queue of indices, kept in decreasing order of their values. Invariant: the front of the deque is always the index of the current window's maximum.

For each index i:

1. Evict from the front if it's out of the window (deque.front <= i - k).
2. Evict from the back while the value there is <= nums[i] — those elements can never be the max again (a newer, larger/equal element exists), so they're useless.
3. Push i onto the back.
4. Once i >= k - 1, the window is full → nums[deque.front] is this window's max.

function maxSlidingWindow(nums, k) {
  const deque = []; // stores indices, values decreasing front->back
  const result = [];
  for (let i = 0; i < nums.length; i++) {
    // 1. drop indices outside the window
    if (deque.length && deque[0] <= i - k) deque.shift();
    // 2. drop smaller values from the back
    while (deque.length && nums[deque[deque.length - 1]] <= nums[i]) deque.pop();
    // 3. add current
    deque.push(i);
    // 4. record the max once the first window is complete
    if (i >= k - 1) result.push(nums[deque[0]]);
  }
  return result;
}

Why it's O(n)

Each index is pushed exactly once and popped at most once across the whole run. The inner while looks scary but its total work over all iterations is bounded by n. So O(n) time, O(k) space (the deque holds at most k indices).

Why store indices, not values

You need indices to know when an element falls out of the window (step 1). Values alone can't tell you that.

Edge cases

• k = 1 → result is the array itself.
• k = nums.length → one window, the global max.
• Duplicates → using <= (not <) in step 2 keeps the deque clean; < also works but leaves stale equal elements.
• Empty array → empty result.

How to answer

"Brute force is O(n·k). The optimal is a monotonic deque of indices kept in decreasing value order, so the front is always the window max. For each element: evict out-of-window indices from the front, evict smaller-or-equal values from the back, push the current index. Each index is pushed and popped at most once → O(n) time, O(k) space. I store indices, not values, so I can detect when something leaves the window."