Sliding window maximum

Hard TimeO(n) SpaceO(k)

Given an array nums and a window width k, return the maximum of every window of that width as it slides from one end of the array to the other. A window of width k over n values gives n − k + 1 answers, in the order the windows appear.

Examples

Example 1

Input
nums = [1, 3, -1, -3, 5, 3, 6, 7]k = 3
Output
[3,3,5,5,6,7]
Six windows, each reporting its largest: [1, 3, −1] → 3, then [3, −1, −3] → 3, and on to [3, 6, 7] → 7.

Example 2

Input
nums = [9, 1, 1]k = 2
Output
[9,1]
Two windows: [9, 1] gives 9 and [1, 1] gives 1.

The Code

function maxSlidingWindow(nums, k) {
  const deque = [];
  const out = [];
  for (let i = 0; i < nums.length; i++) {
    while (deque.length > 0 && deque[0] <= i - k) {
      deque.shift();
    }
    while (deque.length > 0 && nums[deque[deque.length - 1]] <= nums[i]) {
      deque.pop();
    }
    deque.push(i);
    if (i >= k - 1) out.push(nums[deque[0]]);
  }
  return out;
}
maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3);
Done
Step through maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3) call by call

Explanation

Ask which values in a window could ever be its maximum. A value with a bigger one after it is finished: that bigger value is in the window too, and it will still be there after the smaller one has dropped out the far end. So the only values worth remembering are the ones with nothing bigger behind them, which leaves a line falling from the largest down to the newest arrival. The largest is the window’s answer; when the window moves past it, the next one in line takes over, and each new value knocks out everything smaller waiting behind it.

  1. 1

    deque is empty, so position 0 joins it. i has not reached k − 1 yet, so no window is complete and nothing is reported.

    i
    1
    0
    3
    1
    -1
    2
    -3
    3
    5
    4
    3
    5
    6
    6
    7
    7

    deque=[]out=[]

    deque → [0]

  2. 2

    nums[1] is 3, and the back of deque points at a 1. It is smaller and older, so it is popped before 1 joins — it can never be a maximum again.

    1
    0
    i
    3
    1
    -1
    2
    -3
    3
    5
    4
    3
    5
    6
    6
    7
    7

    deque=[0]out=[]

    pop 0 · deque → [1]

  3. 3

    nums[2] is −1, smaller than the 3 in front of it, so it just joins the back. i has reached k − 1, so the first window is complete and the front of deque — nums[1], the 3 — is pushed to out.

    1
    0
    3
    1
    i
    -1
    2
    -3
    3
    5
    4
    3
    5
    6
    6
    7
    7

    deque=[1]out=[]

    deque → [1, 2] · out → [3]

  4. 4

    At i = 4 the front, position 1, has fallen out of the window and is shifted off. Then nums[4] is 5, which pops the −3 and the −1 behind it, and the front is now position 4 itself.

    1
    0
    3
    1
    -1
    2
    -3
    3
    i
    5
    4
    3
    5
    6
    6
    7
    7

    deque=[1, 2, 3]out=[3, 3]

    shift 1 · pop −3, −1 · out → [3, 3, 5]

  5. 5

    The same two rules run to the end — shift the front once it leaves the window, pop anything smaller than what arrives — and out finishes with one answer per window.

    1
    0
    3
    1
    -1
    2
    -3
    3
    5
    4
    3
    5
    6
    6
    i
    7
    7

    deque=[6]out=[3, 3, 5, 5, 6]

    return [3, 3, 5, 5, 6, 7]

More like this

All arrays & loops examples (10) →