Monotonic Queue

Core Concepts

Monotonic Queue — a deque maintained so its elements are always in strictly increasing or strictly decreasing order from front to back; older elements that can no longer be the answer are evicted before new elements are added.

Sliding Window Maximum / Minimum — the canonical application: for a window of size k sliding over an array, the deque front always holds the index of the current window's max (or min), giving O(1) query after O(1) amortised push.

Amortised O(1) push — each element is pushed and popped from the deque at most once across the entire traversal, so total cost for n elements is O(n) regardless of window size.

Deque (double-ended queue) — the backing structure; supports O(1) appendleft/append and popleft/pop; Python's collections.deque is the standard choice.

Stale front removal — when the window slides forward, the front element is removed if its index falls outside the window boundary (dq[0] <= i - k); this is separate from the invariant-maintenance eviction done at the back.

---

Structural Invariants

---

Internal Representation

The deque stores array indices, not values. Values are looked up via arr[dq[...]] as needed. This is the only valid representation because:

• Index is needed for stale-front eviction (compare dq[0] against i - k).
• Value can always be recovered; index cannot be recovered from value alone in arrays with duplicates.

Python: from collections import deque; dq = deque(). The deque is bounded implicitly by the eviction logic — no fixed capacity is set.

---

Types / Variants

See monotonic-stack.md for the stack variant (no front eviction, offline use cases).

---

Topic-Specific Operations

push(i) — evict from the back all indices whose values are dominated by arr[i] (maintaining monotone order), then append i to the back. O(1) amortised.

while dq and arr[dq[-1]] <= arr[i]:
    dq.pop()
dq.append(i)

evict_stale(i, k) — before reading the front, remove it if it's outside the current window. O(1).

if dq and dq[0] <= i - k:
    dq.popleft()

query() — read arr[dq[0]]; this is the window maximum (or minimum for min-queue). O(1). Always call evict_stale before query.

Combined per-iteration order: evict stale front → push new element → if window is full (i >= k - 1), record arr[dq[0]]. Performing push before evict is also valid but query must still happen after evict.

---

Key Algorithms

Sliding Window Maximum (fixed k)

Given array arr and window size k, produce an array of length n - k + 1 where each entry is the max of the corresponding window. Time O(n), space O(k).

Key insight: a smaller element that entered the deque before a larger element can never be the answer for any future window, so it is safely evicted immediately.

dq, res = deque(), []
for i, v in enumerate(arr):
    while dq and arr[dq[-1]] < v: dq.pop()
    dq.append(i)
    if dq[0] == i - k: dq.popleft()
    if i >= k - 1: res.append(arr[dq[0]])

Sliding Window Minimum (fixed k)

Mirror of the maximum variant: evict from back while arr[dq[-1]] > arr[i]. Time O(n), space O(k).

Longest Subarray / Subarray Count with Bounded Max–Min

Find longest subarray where max - min <= limit. Maintain two deques (one max, one min); shrink left pointer when arr[max_dq[0]] - arr[min_dq[0]] > limit. Time O(n), space O(n).

Key insight: both extremes must be tracked simultaneously; a single deque cannot capture both.

DP with Monotonic Queue Optimisation

A DP recurrence of the form dp[i] = max(dp[j]) + cost(i) where j ranges over a sliding window can be reduced from O(n²) to O(n) by maintaining a max-deque over dp values as i advances. Time O(n), space O(n).

Key insight: the window over valid j values slides monotonically with i, so the same front-eviction logic applies to DP indices instead of array indices.

Jump Game / Reachability with Window Constraints

Problems where from index i you can jump to [i+a, i+b]: frame as dp[i] = max(dp[j]) + arr[i] for j in [i-b, i-a]; use monotonic queue on dp values. Time O(n), space O(n).

---

Advanced Techniques

Monotonic Queue + DP (Sliding Window DP)

What it solves: DP transitions where the optimal predecessor lies within a sliding window of indices; naive O(n²) scan becomes O(n).

Core mechanism: maintain a max (or min) deque over dp[j] values; as i advances, add j = i - offset to deque and evict fronts that leave the valid j window.

When to use over simpler alternatives: only when the recurrence has the form dp[i] = opt(dp[j]) + f(i) for j in a contiguous range that shifts with i. If the range is not a sliding window, a segment tree is needed instead.

Complexity: O(n) time, O(n) space — one pass through the DP table.

Two-Deque Technique (Simultaneous Max and Min)

What it solves: constraints that bound both max and min of a subarray (e.g., max − min ≤ limit, or count subarrays where both conditions hold).

Core mechanism: run a max-deque and min-deque in parallel over the same window; the window is valid while arr[max_dq[0]] - arr[min_dq[0]] <= limit; shrink from left when violated.

When to use over simpler alternatives: when a single deque tracking only one extreme is insufficient. If only max or only min is constrained, one deque suffices.

Complexity: O(n) time, O(n) space.

Circular Array Sliding Window

What it solves: sliding window max/min on a circular array (e.g., "wrap-around" windows).

Core mechanism: duplicate the array to length 2n, run the standard deque algorithm with window size k, take the first n results; alternatively process with modular index arithmetic.

When to use over simpler alternatives: only when the problem explicitly allows wrap-around; standard non-circular approach is always simpler.

Complexity: O(n) time, O(k) space.

---

Problem Taxonomy

By Problem Category

Problem Signal → Technique

---

Common Patterns

---

Edge Cases & Pitfalls

• Storing values instead of indices: storing arr[i] in the deque prevents stale eviction because there's no way to check if the element's original position left the window. Always store indices.

• Eviction condition off-by-one: the stale check is dq[0] <= i - k (strictly less than or equal), not < i - k. Using strict < keeps one extra stale element at the front, producing wrong maximums.

• Equal values: evict or keep? For sliding window maximum, pop the back when arr[dq[-1]] <= arr[i] (includes equals). Keeping ties means an older equal index sits in front; it will eventually become stale and cause no bugs, but removing it eagerly keeps the deque smaller and is the conventional choice.

• Querying before the first full window: accessing dq[0] when i < k - 1 is valid deque access but semantically wrong — the window is not yet full. Guard with if i >= k - 1.

• Using < vs <= in back eviction: swapping <= for < in max-deque (or >= for > in min-deque) retains equal elements and can double-count when the problem asks for strictly larger values.

• Not evicting stale front after left-pointer advance: in variable-window problems, advancing the left pointer must be accompanied by checking and evicting the front of both deques. Forgetting one deque silently corrupts the window extremum.

• k larger than array length: if k > n, the window never fills; the result array is empty. Guard with if k > len(arr): return [].

• Single-element array: deque receives one push and one front-read; no eviction occurs. Verify the output guard allows i = 0 >= k - 1 = 0 when k = 1.

---

Implementation Notes

• collections.deque in Python supports O(1) appendleft, append, popleft, pop — use these directly; do not index-insert into the middle.
• deque[0] and deque[-1] are O(1) for Python's deque; deque[i] for arbitrary i is O(n) — never use arbitrary indexing.
• Python has no built-in "monotonic queue" class; always construct from collections.deque manually.
• For DP sliding window, ensure the deque eviction window boundary matches the DP transition range exactly — off-by-one in the range (j >= i - k vs j > i - k) produces subtle wrong answers.
• When combining with two-pointer shrink, both deques must evict independently from their fronts; a shared eviction step is a common bug.
• deque(maxlen=k) does not implement a monotonic queue — it auto-evicts the oldest element but does not maintain the monotone invariant. Never use maxlen for this purpose.

---

Cross-Topic Relations

---

Interview Reference

Must-Know Problems

Core Sliding Window

• Sliding Window Maximum (LC 239) — the canonical problem; implement exactly
• Sliding Window Minimum (variation of 239) — mirror of maximum

Variable Window

• Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit (LC 1438) — two-deque + two-pointer
• Shortest Subarray with Sum at Least K (LC 862) — deque on prefix sums; combines monotonic queue with prefix sums

Sliding Window DP

• Jump Game VI (LC 1696) — sliding window DP with max-deque over dp values
• Constrained Subsequence Sum (LC 1425) — same pattern; max of dp window
• Maximum Points You Can Obtain from Cards — variant with window complement

Harder / Combined

• Max Value of Equation (LC 1499) — monotonic queue on a transformed DP expression
• Minimum Number of Flips to Make Binary String Alternating (LC 1888) — circular window deque
• Count Subarrays Where Max Element Appears at Least K Times (LC 2962) — deque + counting

Clarification Questions to Ask

• Is the window size k fixed or does it vary? (Determines fixed vs. variable window approach.)
• Are there negative values in the array? (Doesn't change the algorithm, but matters for DP transition sign assumptions.)
• Is the array circular (wrap-around allowed)? (Requires doubled-array or modular index trick.)
• "At least K" vs. "exactly K" subarrays — confirm whether inclusion-exclusion is needed.
• For DP problems: what is the valid range of predecessor indices? (Defines the deque window size.)

Common Interview Mistakes

• Storing values in the deque instead of indices — invariably breaks stale removal; stress-test with repeated values to expose this.
• Forgetting the output guard (i >= k - 1) and emitting a result from the very first element when k > 1.
• Using < instead of <= in back-eviction for max-deque, silently retaining dominated elements that produce incorrect answers on all-equal arrays.
• In variable-window problems, advancing the left pointer without evicting the front of the deque — the window range becomes inconsistent.
• Attempting to use heapq with lazy deletion when a simpler O(n) deque solution suffices — correct but O(n log n) and penalised on optimality.
• Forgetting that collections.deque(maxlen=k) is not a monotonic queue and will not maintain the invariant.

Typical Follow-Up Escalations

• "Now do it in O(1) extra space" — not possible for the deque approach (deque is O(k)); clarify that O(k) is already optimal for a streaming solution.
• "What if k varies per query?" — a segment tree or sparse table gives O(log n) or O(1) per arbitrary-range query; the deque approach no longer applies without re-scanning.
• "Extend to 2D sliding window maximum" — apply the 1D deque row-wise then column-wise; O(mn) total.
• "Now return the index of the maximum, not the value" — trivial: dq[0] is already an index; return it instead of arr[dq[0]].
• "What if the array is a stream (online)?" — the deque algorithm is inherently online (processes left to right); no change needed except storing results incrementally.