Stacks & Queues5 min read

Monotonic Queue

A queue that tracks the max or min of a sliding window in constant time

build: \(O(n)\)query: \(O(1)\)push: \(O(1)\) amortizedpop: \(O(1)\) amortizedspace: \(O(k)\)

A monotonic queue is a deque (double-ended queue) where elements are kept in sorted order — increasing or decreasing. It's the go-to tool for the sliding window maximum (or minimum) problem.

The problem it solves

Given an array and a window size k, find the maximum element in every window of size k as it slides across the array.

Example: array = [1, 3, -1, -3, 5, 3, 6, 7], k = 3.

Brute force: For each window, scan all k elements → \(O(n × k)\). With a monotonic queue: \(O(n)\).

◈ Watch monotonic queue

← → arrow keys to step · click elements to interact

How it works — the core trick

Maintain a decreasing deque that stores indices (not values). For each new element entering the window:

Pop from the back while the back element is smaller than the new element. Those elements can never be the maximum — the new element is both newer and larger.
Push the new index to the back.
Pop from the front if that index is outside the current window (it's stale).
The front of the deque is always the index of the window's maximum.

Each index is added and removed at most once, so the total time is \(O(n)\).

Why store indices, not values?

We need to check if an element has slid out of the window. Values don't tell us position — indices do. That's why we store the index and look up the value when needed.

Variations

For sliding window minimum, flip the comparison: pop when back is greater than the new element (keep an increasing deque).
Used in DP optimizations when state transitions depend on a range of previous states.

Note: The front of the monotonic queue is always the answer for the current window — you never need to scan the window again.

Complexity

Process full arrayEach index pushed/popped once

Linear\(O(n)\)

Query window max/minAlways at front of deque

Instant\(O(1)\)

Brute forceScan k items per window

Slow\(O(n×k)\)

Space (deque)Only current window candidates

At most k\(O(k)\)

Sliding Window Maximum

from collections import deque

def sliding_max(nums, k):
    dq = deque()  # stores indices, front is always max
    result = []
    for i, val in enumerate(nums):
        # remove indices outside window
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        # remove smaller elements from back
        while dq and nums[dq[-1]] < val:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

print(sliding_max([1, 3, -1, -3, 5, 3, 6, 7], 3))
# [3, 3, 5, 5, 6, 7]

Output

[3, 3, 5, 5, 6, 7]

Sliding Window Minimum

from collections import deque

def sliding_min(nums, k):
    dq = deque()  # front holds minimum index
    result = []
    for i, val in enumerate(nums):
        while dq and dq[0] < i - k + 1: dq.popleft()
        while dq and nums[dq[-1]] > val: dq.pop()
        dq.append(i)
        if i >= k - 1: result.append(nums[dq[0]])
    return result

print(sliding_min([1, 3, -1, -3, 5, 3, 6, 7], 3))
# [-1, -3, -3, -3, 3, 3]

Output

[-1, -3, -3, -3, 3, 3]

Challenge

Quick check

For array [2, 1, 5, 3, 6] with window size k=3, what is the maximum of the first window [2, 1, 5]?

Monotonic Stack

A stack that stays sorted — used to find the next bigger or smaller element fast

→

Queue

A line of people waiting — the first one in is the first one served

→

Sliding Window

A picture frame scanning over an array to solve sub-array problems in \(O(n)\) time

→