Monotonic deque (sliding window max/min)

How does Monotonic deque (sliding window max/min) work?

The deque holds indices, never values. An index tells you when that element leaves the window.

Before pushing a new index, drop every index at the back whose value is smaller. None of them can be the maximum again.

Push the new index at the back. The values now fall from the front to the back.

Look at the front index. If it has slid out of the window, remove it.

The front now holds the window's maximum. Read it without scanning anything.

Each index is pushed once and popped once. That is what keeps the whole pass linear.

1. deque = [0]A window of 3 over [1, 3, -1, -3, 5]. Index 0 goes in.
2. deque = [1]3 beats the 1 behind it. Index 0 is dropped from the back.
3. deque = [1, 2]The -1 is smaller, so it stays. The window is full and the max is 3.
4. deque = [1, 2, 3]The -3 is smaller again. The front index is still in range.
5. deque = [4]5 beats everything and empties the deque. The max is 5.

function maxSlidingWindow(nums, k) {
    const deque = []; // stores indices, values decreasing
    const result = [];
    for (let i = 0; i < nums.length; i++) {
        while (deque.length && deque[0] <= i - k) deque.shift();
        while (deque.length && nums[deque[deque.length - 1]] < nums[i]) deque.pop();
        deque.push(i);
        if (i >= k - 1) result.push(nums[deque[0]]);
    }
    return result;
}

A worked example of Monotonic deque (sliding window max/min)

Longest stretch within a limit

Find the longest stretch whose largest and smallest values differ by at most a limit.

The stretch has to be contiguous.

Grow a variable window and keep two deques, one for maxima and one for minima.

When the two fronts differ by more than the limit, shrink from the left. Drop a front index once it expires.

function longestSubarray(nums, limit) {
    const maxQ = []; // indices, values falling from front to back
    const minQ = []; // indices, values rising from front to back
    let left = 0;
    let best = 0;

    for (let right = 0; right < nums.length; right++) {
        while (maxQ.length && nums[maxQ[maxQ.length - 1]] <= nums[right]) maxQ.pop();
        while (minQ.length && nums[minQ[minQ.length - 1]] >= nums[right]) minQ.pop();
        maxQ.push(right);
        minQ.push(right);

        while (nums[maxQ[0]] - nums[minQ[0]] > limit) {
            if (maxQ[0] === left) maxQ.shift();
            if (minQ[0] === left) minQ.shift();
            left++;
        }

        best = Math.max(best, right - left + 1);
    }

    return best;
}

When should you use Monotonic deque (sliding window max/min)?

These phrases in a problem statement point here:

• •maximum or minimum of every window of size k
• •sliding window maximum/minimum
• •shortest subarray with a sum at least K
• •need both ends of a queue popped/pushed
• •deque, double-ended queue

What is Monotonic deque (sliding window max/min) confused with?

• Monotonic stack: A stack only ever drops from the top. A deque also drops the front when a value leaves the window.
• Sliding window (fixed size): A rolling sum survives a subtraction. A maximum does not, which is why this exists.
• Binary heap / priority queue: A heap gives the maximum in log n. It cannot delete the element that just left the window.
• Stack (LIFO): A plain stack keeps no order and has one open end. Both limits break this problem.

Common mistakes with Monotonic deque (sliding window max/min)

• Storing values instead of indices

  Without an index you cannot tell when an element expires. Push the position and read the value from it.

• Trimming the front before pushing

  Order matters here. Drop the beaten values at the back first, then check the front.

• Being careless about equal values

  Whether you pop on equality decides which duplicate survives. It matters when the answer is an index.

• Reaching for a heap instead

  A heap cannot remove the element that just left the window. Its deletions are lazy and cost extra.

Which interview problems use Monotonic deque (sliding window max/min)?

• Sliding window maximum: The plain form: read the front at every step.
• Longest subarray with absolute diff within a limit: Two deques, one for each end.
• Shortest subarray with sum at least k: Prefix sums with a rising deque over them.
• Jump game VI: The best score inside the window you can reach.
• Constrained subsequence sum: The same window, run over a DP array.
• Max value of equation: A window over x, keyed by y minus x.
• Sliding window minimum: The same code with the comparison flipped.

What is the time and space complexity of Monotonic deque (sliding window max/min)?

O(n)

n up to 1e6 gives O(n), since each index enters and leaves once. Memory is O(k) for the window.