Sliding Window Maximum

Difficulty: Hard

You're given a list of numbers and a window size k. Imagine a window of size k that starts at the beginning of the list and slides one step to the right at a time, all the way to the end.

For every position of that window, find the maximum value inside it, and return the list of all those maximums, in order.

Examples

Input: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Output: [3, 3, 5, 5, 6, 7]

The first window [1,3,-1] has max 3, the next [3,-1,-3] has max 3, then [-1,-3,5] has max 5, and so on.

Input: nums = [1], k = 1
Output: [1]

Only one window, containing the single element.

Input: nums = [9, 11], k = 2
Output: [11]

Only one window fits (size 2 over a list of length 2), and its maximum is 11.

Constraints

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length

Approach

The direct approach is: for every window position, look at all k elements inside it and find the maximum. That's correct, but it repeats a huge amount of comparison work, since each element gets re-compared in every window it belongs to.

The key insight for the fast approach: once a number in the window is smaller than some more-recent number also in the window, that older, smaller number can never become the maximum of any future window — the more recent, larger number will always still be in the window (or the window will have moved past both). So it can be safely thrown away.

This suggests keeping a deque (a list you can add/remove from both ends) of indices, kept in an order where their corresponding values are strictly decreasing from front to back. When a new number comes in from the right, remove indices from the back of the deque whose values are smaller than the new number (they'll never matter again), then add the new index. Also remove the front index if it has slid outside the current window. After each such update, the value at the front of the deque is exactly the maximum of the current window. Every index is added and removed from the deque at most once, so the whole scan is a single pass.

Solutions

Brute Force — Scan Every Window

For each window position, look at all k elements inside it directly to find the maximum.

function maxSlidingWindow(nums, k) {
  const result = [];

  for (let start = 0; start + k <= nums.length; start++) {
    let windowMax = -Infinity;
    for (let i = start; i < start + k; i++) {
      windowMax = Math.max(windowMax, nums[i]);
    }
    result.push(windowMax);
  }

  return result;
}

Time: O(n * k) · Space: O(1) extra, aside from the output list

Optimal — Monotonic Decreasing Deque

Keep a deque of indices whose values are strictly decreasing from front to back. The front index is always the current window's maximum. Drop smaller values from the back before adding a new one, and drop the front once it slides out of the window.

function maxSlidingWindow(nums, k) {
  const deque = []; // stores indices, values decreasing front to back
  const result = [];

  for (let i = 0; i < nums.length; i++) {
    // Remove indices from the back whose values can't beat the new number
    while (deque.length > 0 && nums[deque[deque.length - 1]] < nums[i]) {
      deque.pop();
    }
    deque.push(i);

    // Remove the front index if it has fallen out of the window
    if (deque[0] <= i - k) {
      deque.shift();
    }

    // Once the first full window is formed, record its maximum
    if (i >= k - 1) {
      result.push(nums[deque[0]]);
    }
  }

  return result;
}

Time: O(n) — each index is pushed and popped from the deque at most once · Space: O(k) for the deque