Monotonic Queue

Intuition

Classic question: given an array and a window size k, report the maximum of every window of k consecutive elements. Rescanning each window costs O(n * k). A monotonic queue does it in O(n).

The key observation: if a newer element x enters the window and an older element y <= x is still inside, y can never again be the maximum. x is at least as large and will stay in the window longer than y. So y can be thrown away immediately.

Keep a deque of candidate indices whose values strictly decrease from front to back:

1. Push at the back: before appending index i, pop from the back every index whose value is <= nums[i] (they are now useless).
2. Expire at the front: if the front index has slid out of the window (front <= i - k), pop it from the front.
3. Read the front: it is the maximum of the current window.

Every index is appended once and removed at most once, so the whole pass is O(n). It is "a queue" because elements leave from the front in arrival order when they expire, and "monotonic" because the back is trimmed to keep values sorted. You need both ends, so use a deque (collections.deque in Python, ArrayDeque in Java, std::deque in C++).

For window minimums, flip the comparison so values increase from front to back.

When to use it in interviews / OAs

• Max or min of every fixed-size window: sliding window maximum, the smallest value in each window, maximum of each block of readings.
• Two-pointer windows that need their max and min: "longest subarray where max - min <= limit" keeps one decreasing and one increasing deque. A mirrored variant asks for the narrowest window (often after sorting points by x) whose max - min reaches a threshold: move the right end until it does, then shrink from the left.
• DP where each state takes the best of the previous k states: dp[i] = nums[i] + max(dp[i-k .. i-1]) (jump game with bounded jumps, constrained subsequence sum). The deque turns O(n * k) into O(n).
• Prefix sums with negative numbers: "shortest subarray with sum at least k". A plain sliding window fails when values can be negative, but a deque of increasing prefix sums works.
• Pairs with a distance constraint: maximize yi + yj + (xj - xi) subject to xj - xi <= k; keep the best yi - xi among points still in range.

If instead you need the nearest larger/smaller element (no window boundary), use a monotonic stack (separate article).

Template

Sliding window maximum, the canonical form:

from collections import deque


def sliding_window_max(nums: list[int], k: int) -> list[int]:
    dq: deque[int] = deque()  # Indices; their values decrease from front to back.
    out = []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:  # Older and not larger: it can never be a window max again.
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:  # The front has slid out of the window.
            dq.popleft()
        if i >= k - 1:
            out.append(nums[dq[0]])  # The front is the maximum of nums[i-k+1 .. i].
    return out


assert sliding_window_max([1, 3, -1, -3, 5, 3, 6, 7], 3) == [3, 3, 5, 5, 6, 7]
assert sliding_window_max([4, 2], 1) == [4, 2]

Variable-size window with both extremes. The right end always advances; the left end advances only while max - min is too large, and indices that fall off the left are dropped from the deque fronts.

from collections import deque


def longest_subarray_within(nums: list[int], limit: int) -> int:
    # Longest window whose max - min <= limit, using two monotonic deques.
    maxq: deque[int] = deque()  # Values decrease front to back.
    minq: deque[int] = deque()  # Values increase front to back.
    left = best = 0
    for right, x in enumerate(nums):
        while maxq and nums[maxq[-1]] <= x:
            maxq.pop()
        maxq.append(right)
        while minq and nums[minq[-1]] >= x:
            minq.pop()
        minq.append(right)
        while nums[maxq[0]] - nums[minq[0]] > limit:  # Shrink from the left until valid.
            left += 1
            if maxq[0] < left:
                maxq.popleft()
            if minq[0] < left:
                minq.popleft()
        best = max(best, right - left + 1)
    return best


assert longest_subarray_within([8, 2, 4, 7], 4) == 2
assert longest_subarray_within([10, 1, 2, 4, 7, 2], 5) == 4

Shortest subarray with sum at least k. For each end j, we want the latest start i with prefix[j] - prefix[i] >= k. Two observations justify both pops: once a start satisfies some end, later ends cannot give it a shorter answer, so it can leave from the front; and an earlier start with a prefix that is not smaller is dominated by a later start with a smaller prefix, so it can leave from the back.

from collections import deque


def shortest_subarray_at_least(nums: list[int], k: int) -> int:
    # Shortest non-empty subarray with sum >= k; works with negative numbers.
    prefix = [0]
    for x in nums:
        prefix.append(prefix[-1] + x)
    dq: deque[int] = deque()  # Indices into prefix, with increasing prefix values.
    best = len(nums) + 1
    for j, pj in enumerate(prefix):
        while dq and pj - prefix[dq[0]] >= k:  # The front start works; any later end would be longer.
            best = min(best, j - dq.popleft())
        while dq and prefix[dq[-1]] >= pj:  # A later, smaller prefix is a strictly better start.
            dq.pop()
        dq.append(j)
    return best if best <= len(nums) else -1


assert shortest_subarray_at_least([2, -1, 2], 3) == 3
assert shortest_subarray_at_least([1, 2], 4) == -1
assert shortest_subarray_at_least([84, -37, 32, 40, 95], 167) == 3

Monotonic queue as a DP accelerator: the deque holds indices of the last k states in decreasing order of dp, so the best predecessor is always at the front.

from collections import deque


def max_jump_score(nums: list[int], k: int) -> int:
    # Start at index 0, jump 1..k steps each time, end at n - 1; maximize the sum visited.
    # dp[i] = nums[i] + max(dp[i-k .. i-1]), with the window max kept in a deque.
    dp = [0] * len(nums)
    dq: deque[int] = deque()  # Indices with decreasing dp values.
    for i, x in enumerate(nums):
        if dq and dq[0] < i - k:  # Evict before reading the front.
            dq.popleft()
        dp[i] = x + (dp[dq[0]] if dq else 0)
        while dq and dp[dq[-1]] <= dp[i]:
            dq.pop()
        dq.append(i)
    return dp[-1]


assert max_jump_score([1, -1, -2, 4, -7, 3], 2) == 7
assert max_jump_score([10, -5, -2, 4, 0, 3], 3) == 17

Complexity

• Time: O(n) per pass. Each index enters and leaves the deque at most once.
• Space: O(k) for a fixed window (the deque never holds more than k indices), O(n) in the prefix-sum and DP versions.
• Compare: a heap with lazy deletion also solves sliding window maximum, in O(n log n). Mention it as a fallback, but the deque is the expected answer.

Common pitfalls

• Forgetting to expire the front. Without the front <= i - k check you return maxima of windows that are too wide.
• Off-by-one on the first window. Results start when i >= k - 1; the window is nums[i-k+1 .. i].
• Storing values instead of indices. With values you cannot tell when the front has left the window. (If you must store values, keep duplicates and compare with the outgoing element.)
• Wrong comparison when trimming the back. For maximum, pop values <= (or <) the newcomer; for minimum, pop values >= (or >). Mixing the two directions silently breaks the order.
• Using a sliding window on negative numbers. "Shortest subarray with sum >= k" needs the prefix-sum deque; the usual expand/shrink window assumes all values are non-negative.
• Order of operations in DP. Expire old indices, read the front to compute dp[i], and only then push i. Pushing first would let dp[i] use itself.

Interview variations

• Sliding window maximum / minimum, max queue (a queue with O(1) max() built the same way).
• Longest continuous subarray with absolute difference <= limit.
• Shortest subarray with sum at least K.
• Jump game VI, constrained subsequence sum (dp[i] = nums[i] + max(0, best in window)).
• Max value of equation with a distance limit on x-coordinates.
• Narrowest window whose max - min reaches a threshold: sort by position, then the two-deque window.
• Sliding window with a cost function, for example "the minimum over each window of size k of a precomputed array", common as a sub-step in harder OA problems.