Pattern 10 of 27

Monotonic Queue

Maintain a deque whose values stay ordered so the maximum or minimum of a moving window is always at the front.

Cost: O(n) time, O(k) space
Problems: 6

When to reach for it

You need the maximum or minimum of every window as it slides.
A dynamic programming step takes the best value from the last k states.
A heap would work, but deleting expired entries is getting messy.

How it works

A monotonic deque is a monotonic stack that also lets old elements expire. Before adding a new index, remove from the back every index whose value can never be the window maximum again, because the new one is both larger and later. Then remove from the front any index that has slid out of the window. The front is always the current maximum, and each index enters and leaves once. The same structure speeds up recurrences shaped like dp[i] = nums[i] + max(dp over the previous k positions).

The template

Written for Sliding Window Maximum (write-up)

from collections import deque

def max_sliding_window(nums, k):
    dq, out = deque(), []             # indices, values decreasing
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()                  # can never be a max again
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()              # slid out of the window
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out

Open in the editor Trace it line by line

Six problems, in learning order

1.Sliding Window MaximumLeetCode 239A decreasing deque whose front is the window maximum.Hard
2.Shortest Subarray with Sum at Least KLeetCode 862An increasing deque of prefix sums; negative numbers are why a plain sliding window fails.Not in the curated 370 yet.Hard
3.Constrained Subsequence SumLeetCode 1425Dynamic programming over the best sum in the last k positions, kept in a decreasing deque.Not in the curated 370 yet.Hard
4.Longest Continuous Subarray With Absolute Diff Less Than or Equal to LimitLeetCode 1438Two deques, one for the maximum and one for the minimum; shrink while their gap exceeds the limit.Not in the curated 370 yet.Medium
5.Max Value of EquationLeetCode 1499Keep the best yi - xi in the window with a deque, then add xj + yj.Not in the curated 370 yet.Hard
6.Jump Game VILeetCode 1696dp[i] is nums[i] plus the maximum of the previous k dp values.Not in the curated 370 yet.Medium

What usually goes wrong

Storing values instead of indices, so you cannot tell when the front has expired.
An off-by-one in the expiry check that keeps the window one element too wide.
Reaching for it when the window is not contiguous in index order.

Monotonic Queue, answered

When should I use the monotonic queue pattern?

You need the maximum or minimum of every window as it slides. A dynamic programming step takes the best value from the last k states. A heap would work, but deleting expired entries is getting messy.

What is the time complexity of monotonic queue?

O(n) time, O(k) space. The same structure speeds up recurrences shaped like dp[i] = nums[i] + max(dp over the previous k positions).

Which problem should I start with for monotonic queue?

Start with Sliding Window Maximum (LeetCode 239, Hard). A decreasing deque whose front is the window maximum. The six problems on this page are in learning order.