Monotonic Queue | Engineering Interview Kit

Concept

If a Monotonic Stack finds the “Next Greater Element” across an entire array, a Monotonic Queue is used to find the Maximum (or Minimum) element inside a moving Sliding Window.

The Monotonic Queue pattern almost always explicitly requires the use of a Deque (Double-Ended Queue) because you need to pop() from the back to maintain monotonic order, but you also need to shift() from the front when elements fall out of the sliding window.

Sliding Window Maximum

Problem: You are given an array nums. There is a sliding window of size k moving from left to right. Return an array of the maximum number in every window.
nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3

The Deque Strategy:
We will maintain a Strictly Decreasing Deque of indices.
The absolute maximum value of the current window will always be sitting at the very Front of the Deque.

Maintain Order: Before pushing a new number onto the Back, we brutally kick out any smaller numbers from the Back. (If a new CEO arrives, all the middle managers who are weaker than him are fired. They can never be the maximum of any future window!).
Evict Old: Check the Front of the Deque. If the index stored there is physically too old (it has fallen outside our window size K), we kick it out from the Front.
Record Max: The index currently sitting at the Front is guaranteed to be the maximum of the current window.

Implementation

// Time Complexity: O(N)
// Space Complexity: O(K) (The deque never holds more than K elements)
function maxSlidingWindow(nums: number[], k: number): number[] {
    const result: number[] = [];
    const deque: number[] = []; // Stores INDICES, not the actual values

    for (let i = 0; i < nums.length; i++) {
        // 1. EVICT OLD: Remove indices from the Front that are out of the window bounds
        if (deque.length > 0 && deque[0] < i - k + 1) {
            deque.shift(); 
        }

        // 2. MAINTAIN ORDER: Remove smaller elements from the Back
        // The new element is nums[i]. Anything smaller in the deque is useless.
        while (deque.length > 0 && nums[deque[deque.length - 1]] < nums[i]) {
            deque.pop();
        }

        // 3. PUSH: Add the current index to the Back
        deque.push(i);

        // 4. RECORD MAX: Once our window has reached size K, start recording!
        // The largest element is always at the Front.
        if (i >= k - 1) {
            result.push(nums[deque[0]]);
        }
    }

    return result;
}

(Note: In JavaScript, calling .shift() on an array is technically $O(K)$ . For small K sizes, this is perfectly fine. In a strict FAANG interview, you should mention that you would use a real Linked-List-based Deque for true $O(1)$ shifts).

Interview Questions

Q: In the Sliding Window Maximum, why do we store the indices in the Deque instead of the actual number values?
A: We must store indices so we can accurately perform the “Evict Old” step.
If we just stored the number 5 in the Deque, and the window slides forward, we have absolutely no way of knowing if that 5 was from index 0 (which has now fallen out of the window and must be evicted) or from index 2 (which is still safely inside the window). By storing the index 0, we can mathematically check 0 < i - k + 1 to instantly know when it has expired.

Q: A problem asks you to find the “Longest Continuous Subarray with Absolute Diff Less Than or Equal to Limit”. How does a Monotonic Queue help?
A: This is LeetCode 1438. To know the “absolute diff” of a dynamic window, you need to know both the absolute Maximum and absolute Minimum values currently inside that window in $O(1)$ time.
You solve this by using Two Monotonic Queues simultaneously! One Decreasing Deque (tracks the Max), and one Increasing Deque (tracks the Min). As your Right pointer expands the window, you update both Deques. You peek at the fronts (Max - Min). If the difference exceeds the limit, you advance the Left pointer, making sure to shift() the fronts of the Deques if Left overtakes their indices.