Sliding Window Maximum

You're given an integer array nums and a window size k. Slide a window of exactly k consecutive elements from the left end of the array to the right end, one position at a time.

Return an array containing the maximum of each window, in order from left to right. There are nums.length - k + 1 windows in total.

The key observation: once a bigger number arrives, every smaller number to its left is useless for the rest of the scan. Any future window that contains the smaller, older number also contains the bigger, newer one, so the older one can never be the maximum again.

So keep only the candidates that could still win: a deque of indices whose values are strictly decreasing from front to back. When a new value comes in, pop smaller (or equal) values off the back, since they've just become useless. Then push the new index. The front of the deque is always the current maximum, and you pop it off the front once it slides out of the window.

Spot this pattern when you need a running max or min over a window that moves in one direction. A heap also works, but the deque throws away dominated values instead of keeping them around.

from collections import deque


def max_sliding_window(nums: list[int], k: int) -> list[int]:
    window = deque()  # indices, values strictly decreasing
    result = []
    for i, num in enumerate(nums):
        if window and window[0] <= i - k:
            window.popleft()
        while window and nums[window[-1]] <= num:
            window.pop()
        window.append(i)
        if i >= k - 1:
            result.append(nums[window[0]])
    return result

function maxSlidingWindow(nums, k) {
  const dq = new Array(nums.length); // indices, values strictly decreasing
  let head = 0;
  let tail = 0;
  const result = [];
  for (let i = 0; i < nums.length; i++) {
    if (head < tail && dq[head] <= i - k) head++;
    while (head < tail && nums[dq[tail - 1]] <= nums[i]) tail--;
    dq[tail++] = i;
    if (i >= k - 1) result.push(nums[dq[head]]);
  }
  return result;
}

Start with the brute force and its O(n · k) cost, then ask what work is repeated: neighboring windows share k - 1 elements. The heap is a reasonable middle step and worth mentioning.

The part interviewers listen for is the dominance argument: "if a newer element is at least as big, the older one can never be a window maximum again, so I can throw it away." Once you've said that, the decreasing deque follows, and the amortized O(n) argument (each index enters and leaves once) is the second thing they'll ask about.