Monotonic Deque

Templates

Sliding Window Maximum / Minimum

Core idea: Maintain a deque that keeps elements monotonically decreasing (for max) or increasing (for min).

while(!dq.empty() && nums[dq.back()] < nums[i])
    dq.pop_back();

dq.push_back(i);

if(dq.front() <= i-k)
    dq.pop_front();

Sliding Window With Min + Max (Two Deques)

Maintain two monotonic deques:

• maxDeque → decreasing
• minDeque → increasing

Used when the condition depends on range inside window.

Typical problem

• Longest Continuous Subarray With Absolute Diff ≤ Limit

Condition:

• maxDeque.front() - minDeque.front() <= limit
• When violated → move l.

Prefix Sum + Monotonic Deque

Used for minimum length subarray satisfying constraint.

Example

• Shortest Subarray with Sum at Least K

Observation:

• prefix[j] - prefix[i] >= K

Deque keeps increasing prefix values.

Why? If prefix[j] <= prefix[i]

• Then i is useless.

Operations

• Pop front when condition satisfied
• Pop back when prefix decreasing

DP Window Maximum

Used when DP depends on max of previous k states.

General recurrence:

• dp[i] = value[i] + max(dp[j]) for j in [i-k, i-1]

Typical problems

• Jump Game VI
• Constrained Subsequence Sum
• Deque keeps max dp values.

DP Window Minimum

Same as pattern 4 but with minimum.

Recurrence:

• dp[i] = value[i] + min(dp[j])

Example style problems:

• Minimum cost path with limited jumps
• Dynamic programming with window constraints

Deque invariant:

• dp[dq[0]] <= dp[dq[1]] <= dp[dq[2]]

Monotonic Queue Optimization for DP

Used to optimize O(nk) DP → O(n).

General structure:

• dp[i] = min(dp[j] + cost(j,i))

If cost has a structure allowing monotonicity → use deque. Common in advanced DP interviews.

Example categories:

• partition DP
• slope optimization problems
• convex DP approximations

Maintaining Candidates for Future Decisions

Sometimes we maintain candidates because future elements will invalidate them.

Example pattern:

while dq not empty and new_value better than dq.back()
    pop_back

Common uses:

• best previous state
• candidate intervals
• monotonic scoring functions

Seen in problems like:

• scheduling
• maximum score path

Increasing / Decreasing Envelope (Competitive Programming Style)

This is a generalized monotonic deque.

Maintain elements satisfying:

• f(a) <= f(b) <= f(c)

Used in:

• DP optimization
• sliding convex hull style problems
• cost functions that grow monotonically

Often appears in hard dynamic programming interviews.

Recognizing the Pattern Quickly

Problem Type	Pattern
Sliding window max/min	Pattern 1
Window constraint with range	Pattern 2
Shortest subarray / prefix condition	Pattern 3
DP with window max	Pattern 4
DP with window min	Pattern 5
DP optimization	Pattern 6
Candidate pruning	Pattern 7
Advanced DP envelope	Pattern 8

The 5 Most Important Ones (Interviews)

You should master these first:

• Sliding Window Max (239)
• Prefix Sum Deque (862)
• Two Deques Window (1438)
• DP Window Max (1696)
• DP Window Max (1425)

Those cover ~90% of real interview questions.

Exercises

• Sliding Window Maximum
• Shortest Subarray with Sum at Least K
• Constrained Subsequence Sum
• Jump Game VI