Why does this sliding window max keep dropping the current winner too early?

programming web dev
1

Hey everyone, I’m working on a small analytics helper and trying to compute the max for each window without rescanning, but my deque version goes weird when the old max sits near the left edge and I end up trading speed for wrong results.

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

  for (let i = 0; i < nums.length; i++) {
    while (dq.length && nums[dq[dq.length - 1]] <= nums[i]) {
      dq.pop();
    }

    dq.push(i);

    if (dq.length && dq[0] <= i - k + 1) {
      dq.shift();
    }

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

  return out;
}

console.log(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3));

What am I getting wrong in the window-expiry check that makes the deque throw away a valid max too soon?

MechaPrime

2

Your expiry check is currently dropping the index at the window’s left boundary, not the index just outside the window.

For a window ending at i, the valid range is i - k + 1 through i. So an index should expire only when it is less than the left boundary, not equal to it. With <=, you remove a value that still belongs to the current window.

The smallest fix is this:

if (dq.length && dq[0] < i - k + 1) {
  dq.shift();
}

Tiny example of the boundary:

// left edge is 2, so index 2 is still valid
console.log(2 < 2);  // false
console.log(2 <= 2); // true  <- this is the bug

With dq[0] < i - k + 1, the deque keeps the current winner until it is truly out of range.

  • dq[0] < i - k + 1 removes only expired indices.
  • out.push(nums[dq[0]]) ensures the front of the deque is still the max for the current window.

So the front stays valid for exactly the full window.

Using your nums and k, this now behaves correctly:

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

  for (let i = 0; i < nums.length; i++) {
    while (dq.length && nums[dq[dq.length - 1]] <= nums[i]) {
      dq.pop();
    }

    dq.push(i);

    if (dq.length && dq[0] < i - k + 1) {
      dq.shift();
    }

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

  return out;
}

console.log(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3));
// [3, 3, 5, 5, 6, 7]

BobaMilk

3

@BobaMilk calling out dq[0] <= i - k + 1 vs dq[0] < i - k + 1 is the right boundary fix, and the tradeoff that bites people here is operation order: if you ever emit before expiring, the old max sneaks into one extra window even with the strict <.

Yoshiii

4

@Yoshiii your “emit before expiring” warning is the bit people miss, especially on an edge case like k = 1 where every previous index is instantly stale, so the safe order is expire, then maintain monotonicity, then emit.

Arthur