Sliding Window Maximum: The Monotone Deque You Actually Need

You've done sliding window. You can track character counts, shrink and expand on a condition, handle frequency maps. A solid sliding window problem? You've got it.

Then the interviewer says: "Now what if you need the maximum value in every window of size k?"

Your first instinct is right — scan the window at each step. O(nk). Interviewers know this and they will ask you to do better. The follow-up is practically guaranteed once you've nailed the basics.

The tool you need is a monotone deque (sometimes called monotonic queue). It's not a new data structure — it's a regular double-ended queue used with a specific discipline. Once you see the pattern, it clicks fast. But getting there requires understanding why some elements in your window can never be the maximum and can safely be discarded.

The Core Idea

A deque supports O(1) add/remove from both ends — something a JavaScript array gives you only at the back, which is why the code below tracks the front with an index instead of calling shift(). The monotone deque for sliding window maximum maintains a deque of indices — specifically, indices in decreasing order of their corresponding values. The front of the deque always holds the index of the current window's maximum.

Two invariants to maintain at each step i:

1. Expired indices: If the front of the deque is outside the current window (deque[front] <= i - k), pop it. It's stale.

2. Dominated elements: Before adding index i, pop from the back anything whose value is ≤ nums[i]. Those elements are behind i in the array, inside the window, and smaller — they will never be the max while i is in the window, so they're useless.

After those two cleanup operations, push i to the back. The front of the deque is your current window's max.

Here's what this looks like with nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3:

The key observation: when we process index 4 (nums[4] = 5), indices 1, 2, and 3 all get popped because their values (3, -1, -3) are smaller than 5. They cannot possibly be the window maximum as long as 5 is in the window — and 5 will still be in the window after they've left.

Each index is pushed exactly once and popped at most once. Total work across all n steps: O(n).

Problem 1: Sliding Window Maximum (LeetCode 239)

The problem: Given array nums and window size k, return an array of max values for each window.

Brute Force

// Time: O(n*k)  Space: O(1)
const maxSlidingWindowBrute = (nums, k) => {
  const result = [];
  for (let i = 0; i <= nums.length - k; i++) {
    let max = -Infinity;
    for (let j = i; j < i + k; j++) {
      max = Math.max(max, nums[j]);
    }
    result.push(max);
  }
  return result;
};

For k = 1000 and an array of 100,000 elements, this is 100 million operations. It times out.

Optimized: Monotone Deque

// Time: O(n)  Space: O(k)
const maxSlidingWindow = (nums, k) => {
  const deque = []; // stores indices, decreasing by value
  let head = 0;     // front cursor — NOT deque.shift(), see the note below
  const result = [];
 
  for (let i = 0; i < nums.length; i++) {
    // 1. Retire indices that fell out of the window (move the cursor, no re-indexing)
    while (head < deque.length && deque[head] <= i - k) {
      head++;
    }
 
    // 2. Remove back indices dominated by nums[i]
    while (deque.length > head && nums[deque[deque.length - 1]] <= nums[i]) {
      deque.pop();
    }
 
    // 3. Add current index
    deque.push(i);
 
    // 4. Reclaim the retired prefix so the array stays O(k) rather than O(n).
    //    One O(k) move per k retirements — amortized O(1) per element.
    if (head > k) {
      deque.splice(0, head);
      head = 0;
    }
 
    // 5. Window is full — record the max
    if (i >= k - 1) {
      result.push(nums[deque[head]]);
    }
  }
 
  return result;
};

Walk through [1, 3, -1, -3, 5, 3, 6, 7], k = 3 (the deque column shows the live window — the indices from head onward):

Result: [3, 3, 5, 5, 6, 7]. Correct.

Problem 2: Longest Continuous Subarray With Absolute Diff ≤ Limit (LeetCode 1438)

This one is the harder application. The constraint is different: find the longest subarray where the difference between the maximum and minimum is ≤ limit.

The naive approach: for every subarray, track max and min. O(n²). You need better.

The insight: maintain two monotone deques simultaneously — one tracking window max (decreasing), one tracking window min (increasing). When max_deque.front - min_deque.front > limit, shrink from the left.

// Time: O(n)  Space: O(n)
const longestSubarray = (nums, limit) => {
  const maxDeq = []; let maxHead = 0; // decreasing — front is max
  const minDeq = []; let minHead = 0; // increasing — front is min
  let left = 0;
  let maxLen = 0;
 
  for (let right = 0; right < nums.length; right++) {
    // Maintain decreasing deque for max
    while (maxDeq.length > maxHead && nums[maxDeq[maxDeq.length - 1]] <= nums[right]) {
      maxDeq.pop();
    }
    maxDeq.push(right);
 
    // Maintain increasing deque for min
    while (minDeq.length > minHead && nums[minDeq[minDeq.length - 1]] >= nums[right]) {
      minDeq.pop();
    }
    minDeq.push(right);
 
    // Shrink window until constraint is satisfied — advance the cursors, no shift()
    while (nums[maxDeq[maxHead]] - nums[minDeq[minHead]] > limit) {
      left++;
      if (maxDeq[maxHead] < left) maxHead++;
      if (minDeq[minHead] < left) minHead++;
    }
 
    maxLen = Math.max(maxLen, right - left + 1);
  }
 
  return maxLen;
};

For nums = [8, 2, 4, 7], limit = 4:

• At right = 3 (value 7): max = 8, min = 2, diff = 6 > 4. Shrink left.
• After shrinking to left = 1: window is [2, 4, 7], max = 7, min = 2, diff = 5 > 4. Keep shrinking.
• After left = 2: window is [4, 7], diff = 3 ≤ 4. Max length = 2.

Each deque carries its own cursor, for the same reason as Problem 1. There's no compaction step here because the annotated O(n) space already covers the retired prefixes — a strictly decreasing array keeps every index in maxDeq, so the deque is O(n) either way. That is also what makes shift() so expensive in this one: on decreasing input with limit = n/2, one front eviction per step off an n/2-long deque runs 0.87ms → 71ms → 281ms → 1,117ms for n = 20,000 → 40,000 → 80,000 → 160,000, against 0.20ms → 0.44ms → 1.00ms → 2.04ms with the cursors. 548× at the top end, and 6.4 billion array slots moved versus none.

The two-deque trick is a pattern: whenever you need to track both max and min of a sliding window in O(n), use two monotone deques.

Problem 3: Jump Game VI (LeetCode 1696)

This one looks like DP, and it is — but naively it's O(n²). The deque makes it O(n).

The problem: You're at index 0 with score 0. On each move, you can jump 1 to k steps forward. Each landing scores nums[i]. Maximize total score.

The DP recurrence: dp[i] = nums[i] + max(dp[i-k], ..., dp[i-1]).

The "max of the last k dp values" is exactly a sliding window maximum on the dp array itself.

// Time: O(n)  Space: O(n)
const maxResult = (nums, k) => {
  const n = nums.length;
  const dp = new Array(n).fill(0);
  dp[0] = nums[0];
 
  const deque = [0]; // indices into dp, front holds max dp index
  let head = 0;      // front cursor, same as Problem 1
 
  for (let i = 1; i < n; i++) {
    // Retire out-of-window dp indices
    while (head < deque.length && deque[head] < i - k) {
      head++;
    }
 
    // Best landing option: dp[front of deque] + nums[i]
    dp[i] = dp[deque[head]] + nums[i];
 
    // Maintain decreasing deque on dp values
    while (deque.length > head && dp[deque[deque.length - 1]] <= dp[i]) {
      deque.pop();
    }
    deque.push(i);
  }
 
  return dp[n - 1];
};

For nums = [1, -1, -2, 4, -7, 3], k = 2:

The deque keeps track of which recent dp value is best to jump from. Same sliding window maximum — just applied to a DP array instead of the input. And the same cursor: dp is already O(n), so the retired prefix is free, and it's the difference between 1,119ms and 2.2ms at n = 160,000 with k = n/2 on input that keeps the deque full (nums[i] = -i, so dp never ties and nothing is ever popped from the back).

This pattern (deque-optimized DP) shows up in Jump Game VIII, Constrained Subsequence Sum (LeetCode 1425), and similar problems where your DP transition looks at the best value in a fixed-size window of previous states.

Interview Tips

Signal pattern recognition early. As soon as you see "sliding window" + "maximum/minimum in window," say out loud: "This looks like a monotone deque problem." You'll get credit for knowing the pattern even before you've written a line.

The deque discipline. The order of operations matters: expire front → maintain back → push current → read front. If you mix these up, you'll get wrong answers. Practice this sequence until it's automatic.

Two common follow-ups after LeetCode 239:

1. "What if the array is a stream (you get values one at a time)?" — same deque, just process online
2. "What's the space complexity?" — O(k) because the deque never holds more than k indices

Recognize the pattern in DP problems. When a DP recurrence is dp[i] = f(max(dp[i-k..i-1])), your first instinct might be "O(n²) DP is unavoidable." It's not. The deque makes it O(n). Jump Game VI is the clearest example, but once you see it once, you see it everywhere.

On the deque.shift() O(n) issue: Bring it up before the interviewer does, because it is the one implementation detail that can invalidate your complexity claim rather than just slow the code down. shift() is O(deque length), the deque holds up to k, so the shift version is O(n × k) — the bound you were hired to beat. The listings above use a front cursor (head++) plus a splice to reclaim the dead prefix; a linked list, ring buffer, or two stacks all work too. Say which one you'd reach for and why, then move on.

The real insight — and this is worth saying in the room — is that the elements you remove from the back when adding a new element are provably useless. They're inside the window, they're smaller than the new element, and they'll leave the window before the new element does. Discarding them is safe and necessary. Once the interviewer hears you articulate why you're popping from the back, they know you understand the structure, not just the code.