Monotonic QueueMonotonic queues

01Why it exists

Reach for it when you see:Maximum or minimum over a sliding window, extrema over a fixed-length range, the last k items, how an extremum updates as a window moves, the range max in a DP transition.

02The core idea

A monotonic queue is a deque whose values decrease from front to back (when you want maximums), which means the front is always the current window's maximum. It uses both ends of the deque: the back maintains the monotonic order, and the front evicts elements that have left the window.

The key observation: when a new element x arrives, everything at the back smaller than x can be thrown away outright. They are smaller than x, and they entered the window earlier so they will leave earlier — so as long as x is around, they can never be the maximum. Drop them, put x on the back, and the queue stays decreasing on its own.

The front has to be checked for having slid out of the window. Since the deque stores indices, pop from the front whenever dq[0] ≤ i − k. Because each index is pushed once and popped at most once, n elements cost O(n) in total, beating both the brute-force O(nk) and the heap-based O(n log k).

How it relates to the monotonic stack: both keep their order by popping the useless entries before a new element goes in. The difference is that a monotonic queue also has to evict expired entries from the front, which is why it needs a deque. Whenever you want an extremum over a range that slides, reach for this first.

03The algorithm

1. 1Build a deque of indices (not values, so you can tell when an entry has expired). Keep the values decreasing for a maximum, increasing for a minimum.
2. 2For each i, clear the back first: while dq and nums[dq[-1]] <= nums[i]: dq.pop(). Using <= evicts older equal elements too, which keeps the queue shorter.
3. 3Push i onto the back.
4. 4Then clear the front: if dq[0] <= i − k: dq.popleft(). At most one entry can expire per iteration, so an if is enough.
5. 5Once i ≥ k − 1 (the window is full), nums[dq[0]] is the answer for that window.

04Interactive demo

Window size 3. Each step first pops everything smaller than the new element off the back (shown struck through), then checks whether the front has expired. Green is the front of the deque, which is the current window's maximum.

05Code

Sliding window maximum and minimum differ by a single comparison operator. The third snippet combines prefix sums with a monotonic queue to solve "shortest subarray with sum at least k", an advanced use of the technique.

from collections import deque

# Sliding window maximum (LeetCode 239).
# The deque holds indices whose values decrease from front to back, so the front is always the window maximum.
def max_sliding_window(nums, k):
    dq = deque()
    out = []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:     # anything at the back smaller than x can never be the maximum again
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:                  # the front has left the window
            dq.popleft()
        if i >= k - 1:                      # only emit once the window is full
            out.append(nums[dq[0]])
    return out


# The same skeleton for minimums: swap <= for >=
def min_sliding_window(nums, k):
    dq = deque()
    out = []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] >= x:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out


# Shortest subarray with sum at least k (LeetCode 862): prefix sums plus a monotonic queue
def shortest_subarray(nums, k):
    p = [0]
    for x in nums:
        p.append(p[-1] + x)
    dq = deque()                            # indices whose prefix sums increase
    best = float("inf")
    for j, pj in enumerate(p):
        while dq and pj - p[dq[0]] >= k:    # the front works as a left end, so settle it: it will never be better
            best = min(best, j - dq.popleft())
        while dq and p[dq[-1]] >= pj:       # anything at the back bigger than me always loses to me as a left end
            dq.pop()
        dq.append(j)
    return best if best != float("inf") else -1

06Practice

• LeetCode 239Sliding Window MaximumHard
• LeetCode 1438Longest Continuous Subarray With Absolute Diff ≤ Limit (maintain a max and a min at once)Medium
• LeetCode 862Shortest Subarray with Sum at Least KHard
• LeetCode 1696Jump Game VI (DP plus a monotonic queue)Medium
• LeetCode 1425Constrained Subsequence SumHard