Monotonic Queue: Sliding Window Maximum

Key Insights

Monotonic queues maintain elements in strictly decreasing (or increasing) order, allowing O(1) access to the maximum while supporting O(n) total operations across all elements
Store indices rather than values in the queue—this elegantly solves the window boundary problem without additional bookkeeping
The key invariant: any element smaller than a new arrival can never be the maximum while the new element remains in the window, so discard them immediately

The Problem That Breaks Naive Solutions

The sliding window maximum problem (LeetCode 239) sounds deceptively simple: given an array of integers and a window size k, return an array containing the maximum value in each window as it slides from left to right.

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]

Window positions:
[1  3  -1] -3  5  3  6  7  → max = 3
 1 [3  -1  -3] 5  3  6  7  → max = 3
 1  3 [-1  -3  5] 3  6  7  → max = 5
 1  3  -1 [-3  5  3] 6  7  → max = 5
 1  3  -1  -3 [5  3  6] 7  → max = 6
 1  3  -1  -3  5 [3  6  7] → max = 7

The naive approach scans each window to find the maximum: O(k) per window, O(n) windows, yielding O(n×k) total time. When k approaches n, this degrades to O(n²). For an array of 100,000 elements with k=50,000, you’re looking at billions of operations. Production systems can’t tolerate this.

You might reach for a max-heap. Clever, but not quite optimal—you’ll hit O(n log k) because removing out-of-window elements requires heap operations. The monotonic queue achieves O(n) by exploiting a crucial insight about which elements actually matter.

Understanding Monotonic Queues

A monotonic decreasing queue maintains elements in strictly decreasing order from front to back. The front always holds the maximum. When you add a new element, you first remove all elements from the back that are smaller than or equal to it.

Why does this work? Consider the window [1, 3, -1]. The value 1 can never be the maximum in any window that also contains 3. Once 3 enters, 1 becomes irrelevant. We can safely discard it.

This is the core insight: an element can only be the maximum if no larger element exists to its left within the window. By maintaining decreasing order, the front is always the current maximum, and the elements behind it are candidates for future maximums as the window slides.

from collections import deque

class MonotonicQueue:
    def __init__(self):
        self.deque = deque()  # stores indices
    
    def push(self, nums: list, i: int) -> None:
        # Remove all elements smaller than the new one
        # They can never be the maximum while nums[i] is in the window
        while self.deque and nums[self.deque[-1]] <= nums[i]:
            self.deque.pop()
        self.deque.append(i)
    
    def pop_front_if_outside(self, left_bound: int) -> None:
        # Remove the front if it's outside the current window
        if self.deque and self.deque[0] < left_bound:
            self.deque.popleft()
    
    def get_max(self, nums: list) -> int:
        return nums[self.deque[0]]

Notice we store indices, not values. This is deliberate—we need to know when elements fall outside the window boundary.

Core Algorithm Walkthrough

Let’s trace through nums = [1,3,-1,-3,5,3,6,7] with k=3. I’ll show the deque contents (as indices) and the corresponding values at each step.

Step 0: Process index 0, value 1
  - Deque empty, push 0
  - Deque: [0] → values: [1]
  - Window not complete yet

Step 1: Process index 1, value 3
  - nums[0]=1 <= 3, pop 0
  - Deque empty, push 1
  - Deque: [1] → values: [3]
  - Window not complete yet

Step 2: Process index 2, value -1
  - nums[1]=3 > -1, don't pop
  - Push 2
  - Deque: [1,2] → values: [3,-1]
  - Window [0,2] complete, max = nums[1] = 3

Step 3: Process index 3, value -3
  - Check front: index 1 >= left_bound 1, keep it
  - nums[2]=-1 > -3, don't pop
  - Push 3
  - Deque: [1,2,3] → values: [3,-1,-3]
  - Window [1,3] complete, max = nums[1] = 3

Step 4: Process index 4, value 5
  - Check front: index 1 < left_bound 2, remove it
  - Deque: [2,3] → values: [-1,-3]
  - nums[3]=-3 <= 5, pop 3
  - nums[2]=-1 <= 5, pop 2
  - Push 4
  - Deque: [4] → values: [5]
  - Window [2,4] complete, max = nums[4] = 5

Step 5: Process index 5, value 3
  - Check front: index 4 >= left_bound 3, keep it
  - nums[4]=5 > 3, don't pop
  - Push 5
  - Deque: [4,5] → values: [5,3]
  - Window [3,5] complete, max = nums[4] = 5

Step 6: Process index 6, value 6
  - Check front: index 4 >= left_bound 4, keep it
  - nums[5]=3 <= 6, pop 5
  - nums[4]=5 <= 6, pop 4
  - Push 6
  - Deque: [6] → values: [6]
  - Window [4,6] complete, max = nums[6] = 6

Step 7: Process index 7, value 7
  - Check front: index 6 >= left_bound 5, keep it
  - nums[6]=6 <= 7, pop 6
  - Push 7
  - Deque: [7] → values: [7]
  - Window [5,7] complete, max = nums[7] = 7

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

Implementation

Here’s the complete, production-ready solution:

from collections import deque
from typing import List

def maxSlidingWindow(nums: List[int], k: int) -> List[int]:
    if not nums or k == 0:
        return []
    
    if k == 1:
        return nums[:]
    
    # Monotonic decreasing deque storing indices
    dq = deque()
    result = []
    
    for i in range(len(nums)):
        # Remove indices outside the current window
        # Window left boundary is i - k + 1
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        
        # Maintain decreasing order: remove smaller elements from back
        while dq and nums[dq[-1]] <= nums[i]:
            dq.pop()
        
        dq.append(i)
        
        # Start recording results once first window is complete
        if i >= k - 1:
            result.append(nums[dq[0]])
    
    return result

import java.util.ArrayDeque;
import java.util.Deque;

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k == 0) {
            return new int[0];
        }
        
        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> deque = new ArrayDeque<>();
        
        for (int i = 0; i < n; i++) {
            // Remove indices outside current window
            while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }
            
            // Remove smaller elements from back
            while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
                deque.pollLast();
            }
            
            deque.offerLast(i);
            
            // Record result once window is complete
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }
        
        return result;
    }
}

Edge cases handled: k=1 returns the original array (every element is its own maximum), k=n returns a single-element array with the global maximum, and duplicate values work correctly because we use <= when removing from the back.

Complexity Analysis

Time Complexity: O(n)

Each element is pushed exactly once and popped at most once. The inner while loops might seem concerning, but they’re amortized O(1). Across all iterations, we perform at most n pushes and n pops total. The outer loop runs n times, so the total is O(n).

Space Complexity: O(k)

The deque never holds more than k elements—any element older than k positions gets removed before we process new elements.

Comparison with Heap-Based Approach:

A max-heap solution achieves O(n log k). You push each element with its index, and lazily remove stale elements when they appear at the top. The log k factor comes from heap insertions. For k=1000 and n=1,000,000, the monotonic queue is roughly 10x faster in practice.

The sliding window minimum requires only flipping the comparison:

def minSlidingWindow(nums: List[int], k: int) -> List[int]:
    dq = deque()
    result = []
    
    for i in range(len(nums)):
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        
        # Changed: maintain increasing order for minimum
        while dq and nums[dq[-1]] >= nums[i]:
            dq.pop()
        
        dq.append(i)
        
        if i >= k - 1:
            result.append(nums[dq[0]])
    
    return result

Related problems worth practicing:

Shortest Subarray with Sum at Least K (LC 862): Uses monotonic deque with prefix sums for variable-size windows
Jump Game VI (LC 1696): DP optimization where monotonic queue tracks maximum reachable score
Constrained Subsequence Sum (LC 1425): Similar DP pattern with sliding window constraint
Longest Continuous Subarray with Absolute Diff ≤ Limit (LC 1438): Requires both monotonic increasing and decreasing queues simultaneously

When to Reach for Monotonic Queues

Recognize these patterns:

Sliding window + range extrema: Any problem asking for min/max over a sliding window
DP optimization: When recurrence involves max(dp[j]) for j in some range relative to i
Next greater/smaller element variants: Though a stack often suffices for simpler cases

Monotonic queue vs. alternatives:

Segment trees: Better for arbitrary range queries with updates, but O(log n) per query
Sparse tables: O(1) queries but O(n log n) preprocessing and no updates
Monotonic queue: Perfect for sliding windows with O(1) amortized per element

The monotonic queue is a specialized tool. When the problem fits—sliding window with order statistics—nothing beats it. Learn to recognize the pattern, and you’ll solve an entire class of problems optimally.