vault

Monotonic Queue Optimization

25 min read

Monotonic Queue Optimization

Monotonic Queue Optimization is the dynamic-programming speedup that collapses an O(n · k) recurrence of the form dp[i] = min_{j ∈ [i - k, i - 1]} (dp[j] + cost(j, i)) (or its max analogue) down to O(n) total — when the cost term cost(j, i) decomposes into a value-at-j part plus a value-at-i part, i.e., cost(j, i) = c1(j) + c2(i). Under that decomposition, the inner min reduces to min_{j} (dp[j] + c1(j)) + c2(i) — a min over a bounded-size sliding window of the function f(j) = dp[j] + c1(j). Maintaining the window’s running min in amortized O(1) per step is exactly what the Monotonic Deque does, so the entire DP runs in O(n). The pattern is the canonical answer to LeetCode 1696 (Jump Game VI) and LC 1425 (Constrained Subsequence Sum), generalizes to arbitrary “DP recurrences with a max/min over a fixed-width or variable-width preceding window,” and crops up in production-leaning problems like minimum-cost speech recognition decoding (HMM Viterbi with an emission window), shortest-path-with-at-most-k-edges DP, and cumulative-revenue DPs in operations research. The one-line recognition signal: the DP state has a window of preceding states, and the inner aggregate is a min or max over that window of an additively-decomposable cost. When you see that, reach for the monotonic deque; the speedup is from O(n^2) or O(nk) to O(n) — orders of magnitude on contest-sized inputs.

1. Intuition — Why a Bounded Window Plus Min/Max Equals Deque

Suppose you are computing a DP over a sequence: dp[0], dp[1], ..., dp[n-1]. The transition has the shape

dp[i] = (something at i) + min_{j ∈ window of i} dp[j]

where “window of i” is some subset of indices preceding i — typically [i - k, i - 1] (last k), or [L, i - 1] for a left endpoint L that grows with i (variable but never decreases). The naïve evaluation scans the window for each i and costs O(k) (or O(L) for the variable case), making the whole DP O(n · k) or O(n^2).

The structural observation that makes the deque work: the window is a sliding window, with elements entering from the right (each new dp[i] becomes a candidate for the next iteration) and exiting from the left (as i advances, the leftmost candidate falls out). The relevant aggregate is min, which is exactly what the Monotonic Deque tracks in O(1) amortized per step.

A real-world analogy: imagine you are running a 30-day stock-trading desk. Each day, you want the minimum closing price over the last 10 days. The naive method scans the last 10 days’ prices and reports the min — O(10) per day, O(300) total. The smarter method maintains a deque of “still-relevant” prices: a price p_j from day j is irrelevant on day i if (a) i - j > 10 (too old) or (b) some later day’s price is lower (a competitor that will dominate p_j for every future query). Each price enters the deque at most once and exits at most once, giving O(1) amortized per day, O(30) total.

The DP version of this is identical, except instead of storing raw prices we store DP values (or dp[j] + c1(j) if there’s a per-j adjustment). The “competitor” relationship is the monotonicity invariant: in a min-deque, if a newer candidate has a smaller value than an older one, the older one will never be the answer (the newer is both more recent — will live longer in the window — and smaller), so we discard the older.

The key facts the deque exploits, summarized:

  1. The window is bounded (so a far-back candidate can be expired without being inspected again).
  2. The aggregate is min (or max), which has a “dominance” property — a smaller value plus a longer remaining lifetime always beats a larger value plus a shorter lifetime.
  3. The cost decomposes as cost(j, i) = c1(j) + c2(i) — only this lets the inner min reduce to a query on a transformed series f(j) = dp[j] + c1(j).

2. The Recurrence Shape That Permits the Optimization

The fundamental recurrence:

dp[i] = c2(i) + min_{j ∈ W(i)} (dp[j] + c1(j))

where:

  • i ranges over 0, 1, ..., n - 1 (the index being computed).
  • c1(j) is any function depending only on j (e.g., 0, or -arr[j], or -arr[j-1]).
  • c2(i) is any function depending only on i (e.g., arr[i], 0, or weight[i]).
  • W(i) ⊂ [0, i - 1] is the window of valid predecessors for i. Standard shapes:
    • Fixed-width window: W(i) = [i - k, i - 1] (the last k indices). LC 1696, LC 1425.
    • Left-monotone variable window: W(i) = [L(i), i - 1] where L(i) is a non-decreasing function. Common when the window is “as far back as some constraint allows,” e.g., farthest j such that prefix[i] - prefix[j] ≥ K.
    • Right-shrinking window: rare in DP, more common in two-pointer settings.

The decomposition cost(j, i) = c1(j) + c2(i) is the non-negotiable condition. If cost(j, i) involves the product or any non-decomposable function of j and i (e.g., cost = arr[j] · arr[i], or cost = (i - j) * something), the deque trick does not apply directly. For those, see Convex Hull Trick (linear-function-of-x_i) and Knuth’s Optimization / Divide and Conquer DP (general quadrangle-inequality cases).

The decomposition’s effect on the inner min:

min_{j ∈ W(i)} (dp[j] + c1(j) + c2(i))
  = c2(i) + min_{j ∈ W(i)} (dp[j] + c1(j))
  = c2(i) + min_{j ∈ W(i)} f(j)        where f(j) := dp[j] + c1(j)

The inner min is now over a scalar series f, which is exactly the sliding-window-min problem. The deque maintains it in O(1) amortized.

3. Tiny Worked Example — LC 1696 Jump Game VI

Problem: given nums = [1, -1, -2, 4, -7, 3] and k = 2, start at index 0; at each step jump to any index in [i + 1, i + k]; maximize total sum.

DP definition: dp[i] = max sum reachable at index i. Recurrence:

dp[0] = nums[0]
dp[i] = nums[i] + max(dp[i-1], dp[i-2], ..., dp[i-k])    for i = 1..n-1

The aggregate is max. Cost decomposition: c2(i) = nums[i], c1(j) = 0, f(j) = dp[j]. Window: [i - k, i - 1]. Naïve: O(n · k). With deque: O(n).

Trace with k = 2. Maintain a max-deque of indices into dp, with dp values strictly decreasing from front to back.

inums[i]Expire (front-pop while front < i - k)dp[i] = nums[i] + dp[deque.front()]Back-pop while dp[back] ≤ dp[i]Push iDeque after
01(n/a)dp[0] = 1empty0[0(1)]
1-1front 0, 0 < 1 - 2 = -1? nodp[1] = -1 + dp[0] = -1 + 1 = 0dp[0] = 1 > 0, no pop1[0(1), 1(0)]
2-2front 0, 0 < 2 - 2 = 0? nodp[2] = -2 + dp[0] = -2 + 1 = -1dp[1] = 0 > -1, no pop2[0(1), 1(0), 2(-1)]
34front 0, 0 < 3 - 2 = 1? yes, pop. front 1, 1 < 1? nodp[3] = 4 + dp[1] = 4 + 0 = 4pop 2 (-1 ≤ 4), pop 1 (0 ≤ 4); empty3[3(4)]
4-7front 3, 3 < 4 - 2 = 2? nodp[4] = -7 + dp[3] = -7 + 4 = -3dp[3] = 4 > -3, no pop4[3(4), 4(-3)]
53front 3, 3 < 5 - 2 = 3? nodp[5] = 3 + dp[3] = 3 + 4 = 7pop 4 (-3 ≤ 7), pop 3 (4 ≤ 7); empty5[5(7)]

Final dp = [1, 0, -1, 4, -3, 7]. Answer: dp[5] = 7. ✓

Confirm with naïve scan: from index 0 (value 1), jump to index 1 (-1) → sum 0, then to 2 (-2) → -2, … actually best is 0→1→3→5: 1 + (-1) + 4 + 3 = 7. Or 0→2→3→5: 1 + (-2) + 4 + 3 = 6. The DP correctly identifies the first path as optimal at value 7. ✓

Total deque operations: 6 pushes (one per i) + 4 pops (3, 4, 5 from back; one from front at i = 3). Total work O(n).

4. Pseudocode — The Generic Pattern

The maximum-aggregate version (the minimum version flips comparators):

DP_with_window_max(n, c1, c2, W):
    deque := empty deque of indices, with dp[index] strictly decreasing front→back
    dp := array of length n
    initialize boundary cases (dp[0], possibly dp[1], etc.)
    push initial valid index (typically 0) into deque
    for i := first uncomputed index .. n - 1:
        # Step 1: expire indices that fell out of window W(i)
        while deque not empty AND deque.front() ∉ W(i):
            deque.pop_front()
        # Step 2: read dp[i] using the front (which is the index achieving max f(j) over W(i))
        j_star := deque.front()
        dp[i] := c2(i) + (dp[j_star] + c1(j_star))           # = c2(i) + f(j_star)
        # Step 3: maintain monotonic-decreasing invariant on f-values
        while deque not empty AND f(deque.back()) ≤ f(i):     # f(i) := dp[i] + c1(i)
            deque.pop_back()
        # Step 4: push the current index
        deque.push_back(i)
    return dp[n - 1]   # or whatever final answer the problem requires

Why each step is correct:

  • Step 1 removes any front index that is no longer a valid predecessor for i (out of window). Because the deque holds indices in increasing order, only the front needs checking — any index further back is also further forward in time, and if the front is in the window, all are.
  • Step 2 reads the answer. The deque’s front is the index j* with the maximum f(j) = dp[j] + c1(j) among valid predecessors. Add c2(i) to get dp[i].
  • Step 3 restores the monotonicity invariant. Any back-of-deque index j_back with f(j_back) ≤ f(i) is dominated: for every future iteration that can still see j_back, i is also visible (because i > j_back and the window slides forward). Since f(i) ≥ f(j_back), i is a strictly better candidate; discard j_back permanently.
  • Step 4 appends i to the back. The new state preserves the invariant.

Two invariants (after each iteration):

I1. Index ordering: the deque’s indices are strictly increasing front to back. I2. Value ordering (max-deque): f(deque[k]) is strictly decreasing in k (front to back).

I1 follows from always appending the current index i at the back. I2 is enforced by the back-pop loop in Step 3.

5. Python Implementations

5.1 LC 1696 Jump Game VI — Fixed Window of Size k

from collections import deque
 
def max_result(nums: list[int], k: int) -> int:
    n = len(nums)
    dp = [0] * n
    dp[0] = nums[0]
    dq: deque[int] = deque([0])             # holds indices; dp values strictly decreasing front→back
    for i in range(1, n):
        # Step 1: expire indices outside [i - k, i - 1]
        while dq and dq[0] < i - k:
            dq.popleft()
        # Step 2: dp[i] = nums[i] + max over window
        dp[i] = nums[i] + dp[dq[0]]
        # Step 3: maintain monotonicity (max-deque, so pop while back ≤ current)
        while dq and dp[dq[-1]] <= dp[i]:
            dq.pop()
        # Step 4: push
        dq.append(i)
    return dp[n - 1]

Note the order: read dp[i] using the deque (Step 2), then update the deque to include i (Steps 3 + 4). Reversing this order would let i participate in its own predecessor lookup, which is wrong (you cannot reach i from itself).

5.2 LC 1425 Constrained Subsequence Sum — Variant With max(0, ...) Floor

Problem: given nums and k, find the maximum sum of a subsequence such that consecutive picks are at most k apart. Recurrence:

dp[i] = nums[i] + max(0, max(dp[i-1], dp[i-2], ..., dp[i-k]))

The max(0, ...) handles the empty-subseq-suffix case (start a new subsequence at i).

from collections import deque
 
def constrained_subset_sum(nums: list[int], k: int) -> int:
    n = len(nums)
    dp = [0] * n
    dp[0] = nums[0]
    dq: deque[int] = deque([0])
    best = dp[0]
    for i in range(1, n):
        while dq and dq[0] < i - k:
            dq.popleft()
        dp[i] = nums[i] + max(0, dp[dq[0]])
        best = max(best, dp[i])
        while dq and dp[dq[-1]] <= dp[i]:
            dq.pop()
        dq.append(i)
    return best

The answer is the max of dp[i] over all i (any index can end the subsequence), not dp[n-1]. Track best along the way.

5.3 LC 862 Shortest Subarray with Sum ≥ K — Deque on Prefix Sums

Not a typical “DP” but the same monotonic-deque structural pattern applied to prefix sums. Find the shortest contiguous subarray with sum ≥ K. Define prefix[i] = nums[0] + ... + nums[i-1]. Then subarray sum [j, i) is prefix[i] - prefix[j]. We want min(i - j) such that prefix[i] - prefix[j] ≥ K, with j ≤ i.

from collections import deque
 
def shortest_subarray(nums: list[int], k: int) -> int:
    n = len(nums)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]
    dq: deque[int] = deque()                 # increasing prefix-sum order, front to back
    best = n + 1
    for i in range(n + 1):
        # Pop from front while a valid (j, i) pair is found
        while dq and prefix[i] - prefix[dq[0]] >= k:
            best = min(best, i - dq.popleft())
        # Maintain increasing prefix order (back-pop if dominated)
        while dq and prefix[dq[-1]] >= prefix[i]:
            dq.pop()
        dq.append(i)
    return best if best <= n else -1

The two pop-loops correspond to (a) extracting the answer for any old j already satisfying the constraint with the current i, and (b) discarding old js dominated by i as a future candidate. See Monotonic Deque §5.2 for the deeper explanation.

5.4 Generic Wrapper for “DP With Sliding-Window Aggregate”

from collections import deque
from typing import Callable
 
def dp_window_max(
    n: int,
    initial: float,                       # dp[0]
    c2: Callable[[int], float],           # cost depending on i
    f: Callable[[int, list[float]], float],  # f(j, dp) = dp[j] + c1(j); reads dp
    window: Callable[[int], tuple[int, int]],  # returns [L(i), R(i)] valid predecessor range
) -> list[float]:
    """Generic DP with sliding-window-max optimization. dp[i] = c2(i) + max f(j) over window(i)."""
    dp = [0.0] * n
    dp[0] = initial
    dq: deque[int] = deque([0])
    for i in range(1, n):
        L, _R = window(i)
        while dq and dq[0] < L:
            dq.popleft()
        dp[i] = c2(i) + f(dq[0], dp)
        while dq and f(dq[-1], dp) <= f(i, dp):
            dq.pop()
        dq.append(i)
    return dp

This is rarely worth writing in production (the abstractions cost more than they save), but it makes the shape explicit.

6. Complexity — The Amortized O(n) Argument

Time: O(n) total. Same amortized argument as Monotonic Deque:

Define potential Φ = current deque size. Per outer iteration:

  • Real cost: 1 + f_i + b_i (one push plus front-pops f_i plus back-pops b_i).
  • ΔΦ = +1 - f_i - b_i.
  • Amortized cost = real cost + ΔΦ = 2.

Total amortized cost over n iterations = 2n, plus a possible final flush of ≤ n remaining deque entries. Total real cost ≤ 3n = O(n).

Equivalently — and this is the argument most sources state directly — each index is pushed at most once and popped at most once, totaling at most 2n deque operations across the entire DP. Each operation is O(1) (with a collections.deque in Python or an array with two pointers in C). So total work is O(n). This is precisely the reasoning cp-algorithms gives for the sliding-window-minimum / monotonic-queue construction: because in the index-storing deque “every element can only be pushed and popped once,” each operation is O(1) amortized and “the complexity of the whole algorithm will be O(n)” (cp-algorithms: minimum stack / minimum queue). The potential-function bound above is just a more formal restatement of the same push-once/pop-once accounting.

This is identical to the analysis behind LC 239 Sliding Window Maximum — the bare, no-dp special case where c1(j) = c2(i) = 0 and you simply report the window max each step. The monotonic-deque DP here is LC 239 with a payload: instead of comparing raw array values you compare f(j) = dp[j] + c1(j), but the deque mechanics, the dominance argument, and the push-once/pop-once amortization are exactly the same. The relationship to a Monotonic Stack is also worth naming precisely: a monotonic stack is one-ended (push/pop at the same end) and answers “nearest greater/smaller element” queries with no expiry; a monotonic queue (deque) adds a second end so that stale candidates can expire from the front as the window slides. The deque is the stack generalized with a windowed-expiry front — same dominance invariant, one extra exit.

Space: O(k) for the deque (since at most k valid candidates can coexist), plus O(n) for the dp array. For variable-window problems where the left endpoint can lag arbitrarily, space is O(n) worst-case (the deque can hold all of dp if it’s strictly monotone in the wrong direction).

Speedup over naïve. Naïve O(n · k) for n = 10^5, k = 10^4 is 10^9 ops — too slow for a contest’s 1–2 second time limit. The deque version is O(10^5), finishing in ~10 ms. Four orders of magnitude on contest-sized inputs.

7. Variants and Sub-patterns

7.1 Min-Aggregate vs Max-Aggregate

Flip the comparator in Step 3. Min-deque maintains f strictly increasing front to back; the front is the running min. Max-deque, mutatis mutandis. The invariant changes; the asymptotics don’t.

7.2 Variable-Width Window with Monotonic Left Endpoint

If the window is [L(i), i - 1] with L non-decreasing, the deque still works — Step 1’s expire condition becomes while dq and dq[0] < L(i). Each index still expires at most once. Total O(n).

If L is non-monotone (it can decrease), the deque doesn’t directly work; the abandoned candidates can become valid again. Use a different structure (sorted multiset, segment tree).

7.3 Combined With Prefix Sums

Many problems where the “DP-shaped” recurrence isn’t immediately apparent become deque-tractable after a prefix-sum transform. LC 862 (§5.3) is the canonical example. The transform subarray_sum[j..i] = prefix[i+1] - prefix[j] turns “find subarray with sum ≥ K” into a sliding-window-min query on prefix.

7.4 Combined With Sliding Window

When the problem combines a sliding window with a DP over the window — e.g., “largest sum subarray of length ≤ K” — chain prefix-sums + monotonic deque + window arithmetic. The deque stores prefix indices; the answer at index i is prefix[i] - min(prefix[i - K..i - 1]).

7.5 Generalization to 2D (Sliding 2D Window)

For 2D max/min over a k × k window, apply the 1D deque first along rows (for each row, compute row-max/min over the column window), then along columns of the row-aggregated result. Time: O(rows · cols) = O(N) for an N-cell grid.

7.6 LC 918 Maximum Sum Circular Subarray (Variant)

The standard solution uses Kadane’s Algorithm twice (for max-subarray and min-subarray-to-subtract-from-total). A direct deque solution exists for the circular version: double the array arr + arr[:-1], compute prefix sums, and run a sliding-window-min on prefix to get max subarray of length ≤ n. The deque pattern shines here when the constraint involves an explicit window length.

7.7 LC 1499 Max Value of Equation

Find max y_i + y_j + |x_i - x_j| over (i, j) with |x_i - x_j| ≤ k and i < j. Re-write as (y_j - x_j) + (y_i + x_i) (assuming i < j); the first term depends on j, second on i. Maintain a deque of j indices in decreasing y_j - x_j order, with the window constraint x_i - x_j ≤ k. Same recipe as Jump Game VI with cost decomposition c1(j) = -x_j, c2(i) = y_i + x_i + (max f(j)).

7.8 Production Use: Speech Recognition HMM Decoding

In Hidden Markov Model decoding (Viterbi), if the emission probability has a finite “look-back” window (e.g., HMM-with-bigram-emission-windows), the inner max-over-states-in-window is a monotonic-deque candidate — though in practice HMM decoders use specialized lattice search with beam pruning, not deque optimization, because the state space is multi-dimensional.

7.9 Constrained Shortest-Path with ≤ k Edges

Bellman-Ford with edge-budget constraint: dp[v][k] = min over neighbors u of dp[u][k - 1] + edge(u, v). When the recurrence projects onto a 1D index (e.g., for chain graphs), the deque optimization applies.

8. Pitfalls

8.1 Reading dp[i] After Updating the Deque With i

The deque is for predecessors of i, not i itself. Step 2 (read dp[deque.front()]) must happen before Step 3 (push i). Otherwise the deque might return i as its own predecessor, giving dp[i] = c2(i) + dp[i] + c1(i) — nonsense.

8.2 Off-by-One in the Window Bound

For window [i - k, i - 1], an index j is out of window iff j < i - k. Step 1’s check is dq[0] < i - k (or <= if your window is [i - k + 1, i] etc. — depends on whether i itself is allowed as a predecessor, which it usually isn’t). Trace by hand on small n to verify.

8.3 Forgetting the c2(i) in Step 2

dp[i] = c2(i) + f(j*) — the per-i term must be added back after retrieving the windowed min/max. Forgetting c2(i) produces a DP whose dp[i] equals just the windowed predecessor min, which is wrong. Easy to miss when transcribing from a generic template.

8.4 Wrong Aggregate Direction (Min vs Max)

For LC 1696 we want max; for LC 862 (extracting the shortest subarray with sum ≥ K) we maintain a monotonic-increasing prefix-deque to find a small prefix[j] — the goal is to find, for each i, the j with prefix[j] small enough that prefix[i] - prefix[j] ≥ K and i - j is small. Confusing min vs max swaps the comparator and breaks the invariant. Always think through the dominance argument explicitly.

8.5 Storing Values Instead of Indices

The deque must store indices so Step 1 (expiration) can compare against i - k. Storing values loses the timing information. Recover values via dp[deque[0]] when needed.

8.6 Not Handling Empty Deque

After Step 1, if all indices expired and the deque is empty, Step 2 (dp[i] = c2(i) + f(deque.front())) will throw or read garbage. For typical fixed-window problems with the convention W(i) = [i - k, i - 1] for i ≥ k - 1, the deque always has at least one valid candidate; but for variable-window or boundary-condition-heavy problems, guard with if dq: and handle the empty case (often using a sentinel or the “start fresh at i” base case).

8.7 Confusing With Convex Hull Trick

If the cost is cost(j, i) = a_j · x_i + b_j (linear function of i’s coordinate, with j-dependent slope and intercept), the right optimization is the Convex Hull Trick, not monotonic deque. The deque assumes the cost decomposes additively into c1(j) + c2(i); CHT handles the multiplicative case.

8.8 Mistaking the Window for the Output Range

Some problems’ “window” is an output constraint (e.g., “subsequence has gaps ≤ k”), not a state-window. Confusing the two leads to wrong DP definitions. Always articulate the DP state and the window of valid predecessors separately before writing code.

8.9 Using Python’s list Instead of collections.deque

list.pop(0) is O(n). A monotonic-queue DP using list.pop(0) becomes O(n^2). Always from collections import deque.

8.10 Forgetting to Track the Best Across All Indices

For LC 1425 (and analogous “max subsequence ending anywhere”), the answer is max(dp[i]) over all i, not dp[n - 1]. Track a running best; don’t assume the last index.

9. Diagram — DP Trace for LC 1696 with k=2

flowchart TD
    A["i=0: dp[0]=1; DQ=[0(1)]"]
    B["i=1: expire none; dp[1]=nums[1]+dp[front=0]=-1+1=0; back-pop: 1>0 stop; push 1; DQ=[0(1),1(0)]"]
    C["i=2: expire 0<0? no; dp[2]=-2+dp[0]=-1; back-pop: 0>-1 stop; push 2; DQ=[0(1),1(0),2(-1)]"]
    D["i=3: expire 0<1 yes pop; 1<1? no; dp[3]=4+dp[1]=4; back-pop: 2(-1)≤4 pop, 1(0)≤4 pop; empty; push 3; DQ=[3(4)]"]
    E["i=4: expire 3<2? no; dp[4]=-7+dp[3]=-3; back-pop: 4>-3 stop; push 4; DQ=[3(4),4(-3)]"]
    F["i=5: expire 3<3? no; dp[5]=3+dp[3]=7; back-pop: 4(-3)≤7 pop, 3(4)≤7 pop; empty; push 5; DQ=[5(7)]"]
    G["Answer: dp[n-1] = dp[5] = 7"]

    A --> B --> C --> D --> E --> F --> G

What this diagram shows. A six-step trace of the deque-optimized DP for Jump Game VI on nums = [1, -1, -2, 4, -7, 3] with k = 2. Each box is one outer-loop iteration i, listing: (1) the front-end expiration check (drop indices outside [i - k, i - 1]); (2) the dp[i] computation, which reads the deque’s front index — guaranteed to hold the maximum dp[j] over the current window — and adds nums[i]; (3) the back-end domination pops (drop indices j_back with dp[j_back] ≤ dp[i], since they can never beat i as a future candidate); (4) the push of i onto the back. Notice the moments at i = 3 and i = 5: the new dp value is high enough to dominate every previous candidate, leading to a complete deque clean-out — the deque oscillates between long monotone runs (after a “flat” stretch of low DP values) and a single-element state (right after a new running maximum). The total pushes are n = 6; total pops across both ends are also bounded by n. Thus total work is O(n), an n / k improvement over the naïve O(n · k) scan.

10. Common Interview Problems

ProblemLeetCode # / SourceCost decompositionWindow
Jump Game VILC 1696c2(i) = nums[i], c1(j) = 0[i - k, i - 1] (max)
Constrained Subsequence SumLC 1425c2(i) = nums[i], c1(j) = 0, with max(0, ...) floor[i - k, i - 1] (max)
Sliding Window MaximumLC 239Trivial — just read window max[i - k + 1, i]
Shortest Subarray with Sum ≥ KLC 862Prefix-sum form with two-loop dequeleft endpoint moves; deque on prefix
Longest Subarray with Abs Diff ≤ LimitLC 1438Two deques (max + min), variable leftvariable
Maximum Sum Circular SubarrayLC 918Doubled-prefix technique≤ n length
Max Value of EquationLC 1499c1(j) = -x_j, c2(i) = x_i + y_i + max(y_j - x_j)x_i - x_j ≤ k
Sum of Subarray Minimums (variant)LC 907Combined with monotonic stackn/a
Min Cost to Cut a StickLC 1547Different optimization (interval DP / Knuth)n/a
Frog Jump K Steps (CSES Coin Combinations)CSESStandard window-DPfixed k
Codeforces 372C (Watching Fireworks)CFWindow-DP with adjacent constraintfixed
Codeforces 1077F2 (Pictures with Kittens)CFWindow-DP with item countfixed

The pattern is heavily represented in competitive programming and shows up in mid-to-senior interviews at companies that ask LeetCode-Hard questions (Google, Meta, Citadel, DE Shaw). Recognition signal in interview: “DP recurrence has a min/max over a fixed-size or non-decreasing-left-endpoint window of preceding states, plus an additive per-i term.”

11. When Monotonic Queue Optimization Does Not Apply

The signal that something else is needed:

  • Cost is not additively decomposable: cost(j, i) = arr[j] · arr[i], or cost(j, i) = (i - j)^2, or other non-separable forms. Use Convex Hull Trick (linear in x_i) or Knuth’s Optimization / Divide and Conquer DP (general quadrangle-inequality cases).

  • Aggregate is not min/max: e.g., sum, count, median, kth-percentile. Use Prefix Sums for sums, Two Heaps Pattern for medians, sorted multiset / Segment Tree for kth-percentile.

  • Window is not monotone in left endpoint: a “remembered” candidate that was dominated could become valid again. Use sorted multiset, Segment Tree, or Sparse Table for static range queries.

  • Multi-dimensional state: e.g., dp[i][j] with windowed transitions in both axes. Sometimes resolvable by applying 1D deque optimization independently along each dimension; often not.

  • Random access into the window’s history: deque doesn’t support O(1) index-into-the-middle. Use Sparse Table for static range max/min, Segment Tree for dynamic.

12. Open Questions

  • Can monotonic-queue optimization be combined with Convex Hull Trick for hybrid recurrences? In principle yes — track a deque of slopes plus a window. In practice, problems falling into this exact niche are rare; usually one or the other suffices.
  • What’s the right preconditioning for variable-window DPs whose left endpoint is almost monotone (with rare backward steps)? Current best practice: re-initialize the deque from scratch at each backward step. Amortized still good if backward steps are rare.
  • When does an offline batched approach (precompute window aggregates with Sparse Table for all (L, R) of interest, then read them in order) beat the deque? For static, pre-known windows the sparse-table is O(n log n) preprocessing + O(1) per query — O(n log n) total, log-factor worse than deque’s O(n). The deque wins asymptotically, though Sparse Table’s lower per-query constant can win for small n.
  • In an online / streaming setting, does the monotonic-queue approach extend to “approximate” max/min queries with bounded error? The classical deque is exact; approximate variants (count-min sketches, etc.) trade exactness for sub-linear space but are not used in DP optimization to date.

Picking the right DP-optimization technique

The crossover between monotonic-queue optimization and the other DP-speedup families is determined entirely by the structural form of the cost function, and the boundaries are well-established (cp-algorithms: divide-and-conquer DP):

  • Additively decomposable cost(j, i) = c1(j) + c2(i) → monotonic-queue (this note): the inner min/max becomes a sliding-window query on f(j) = dp[j] + c1(j), giving O(n).
  • Linear in i’s coordinate cost(j, i) = a_j · x_i + b_j (a j-indexed line evaluated at x_i) → Convex Hull Trick; CHT applies “specifically when cost functions are linear,” a stricter requirement than the quadrangle inequality.
  • Satisfies the quadrangle inequality C(a,c) + C(b,d) ≤ C(a,d) + C(b,c) for a ≤ b ≤ c ≤ d, which forces the optimal split point to be monotone (opt(i, j) ≤ opt(i, j+1)) → Knuth’s Optimization (O(n^2)) or Divide and Conquer DP (O(mn log n)).

Misclassifying the cost form leads to wrong asymptotics or wrong answers, so verify which of these three forms the cost matches before committing to the deque. This is a settled taxonomy, not an open question.

13. See Also

Graph View

Backlinks