Sliding Window Maximum

HardSliding WindowArraySliding WindowHeapMonotonic Queue

Problem

You are given an array and a window size. As a window of that fixed size slides across the array from left to right, one position at a time, report the maximum value inside the window at each position.

Example. For [1, 3, -1, -3, 5, 3, 6, 7] with window size 3, the maximums at each position are [3, 3, 5, 5, 6, 7].

Key idea

Recomputing the maximum by scanning the whole window at every position costs O(n · k). The improvement uses a double-ended queue storing array indices rather than values, kept so the values at those indices are always in decreasing order from front to back. When a new index arrives, first discard indices from the back whose values are smaller: they are now permanently useless, since the new, later, larger value will outlast them in every future window. Then append the new index. Before reading the maximum, also discard the front index if it has slid outside the window's left boundary. Under this invariant, the front of the deque always holds the current window's maximum, because anything that could have beaten it was already removed.

Solution

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

  for (let i = 0; i < nums.length; i++) {
    // drop smaller trailing values; a later, larger value outlasts them anyway
    while (deque.length > 0 && nums[deque[deque.length - 1]] < nums[i]) {
      deque.pop();
    }
    deque.push(i);

    // front index has slid outside the window's left boundary
    if (deque[0] <= i - k) {
      deque.shift();
    }

    if (i >= k - 1) {
      result.push(nums[deque[0]]);
    }
  }

  return result;
}

Complexity

  • Time: O(n). Each index is appended to the deque once and removed from it at most once, across the whole array.
  • Space: O(k). The deque holds at most one index per position in the current window.

Watch out for

  • Store indices in the deque, not raw values, so that elements which have aged out of the window on the left can be detected and dropped.
  • Discard smaller trailing values from the back before appending the new index, or the decreasing-order invariant breaks and the front stops being the true maximum.
  • Only start recording output once the first full window has been seen, not from the very first element.

Pattern

This is the monotonic deque pattern: maintain candidates in sorted order while a window slides, discarding any candidate that can never again be the answer. The same idea, run in increasing order instead of decreasing, solves sliding-window minimum and related next-greater-element style problems.

Related questions