Pattern #19

Monotonic Queue

Important interview questions, thinking patterns, sliding window max/min, DP state optimization, and rules for solving monotonic queue problems in Go.

Must Solve

10 core questions — solve these first.

1.Sliding Window Maximum
Monotonic decreasing index queuehard
2.Sliding Window Minimum
Monotonic increasing index queuemedium
3.Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit
Two Monotonic Queues (maxQueue & minQueue)medium
4.Jump Game VI
DP + Monotonic Queue max window scoremedium
5.Constrained Subsequence Sum
DP + Monotonic Queue max subarray sumhard
6.Shortest Subarray with Sum at Least K
Prefix Sum + Monotonic Increasing Queuehard
7.Max Value of Equation
Monotonic Queue storing (y_i - x_i, x_i)hard
8.Maximum Number of Robots Within Budget
Monotonic Queue max charge time + Prefix Sumhard
9.Continuous Subarrays
Two Monotonic Queues tracking window max/min diff <= 2medium
10.Minimum Number of K Consecutive Bit Flips
Monotonic / Deque flip state bufferhard

Also Important

5 more questions worth practicing.

11.First Negative Integer in Every Window
Monotonic / Deque storing negative indicesmedium
12.Maximum of All Subarrays of Size K
Monotonic decreasing index queuemedium
13.Moving Average from Data Stream
Queue / Sliding window stream averageeasy
14.Minimum Cost to Reach End Variants
DP + Monotonic Queue minimum window costmedium
15.DP + Sliding Window Maximum Problems
Dynamic Programming state window max optimizationhard

How to Think

Need maximum in every window?Monotonic Queue (Decreasing)
Need minimum in every window?Monotonic Queue (Increasing)
Need sliding window + fast max/min?Sliding Window + Monotonic Queue
Need best value from last K positions?DP + Monotonic Queue
Need remove old values automatically?Store INDEXES on Queue

Go Monotonic Queue Template (Sliding Window Max)

Standard 4-Step Monotonic Queue Pattern in Go

deque := []int{} // Stores INDEXES

for i := 0; i < len(nums); i++ {
    // 1. Expired? -> Remove from FRONT (deque[0] <= i - k)
    for len(deque) > 0 && deque[0] <= i-k {
        deque = deque[1:]
    }

    // 2. Weaker than current? -> Remove from BACK
    for len(deque) > 0 && nums[deque[len(deque)-1]] <= nums[i] {
        deque = deque[:len(deque)-1]
    }

    // 3. Push current index to BACK
    deque = append(deque, i)

    // 4. Front is maximum for current window!
    // maxVal = nums[deque[0]]
}

👉 Total Time: O(n) | Space: O(k) (Each element is pushed once & popped once)

Monotonic Queue vs Normal Queue vs Monotonic Stack

Normal Queue

Keeps arrival order strictly (FIFO). Used in BFS.

Monotonic Queue

Keeps only useful values in sorted order inside a moving window.

Monotonic Stack

Finds nearest next/previous greater or smaller element.

DP + Monotonic Queue Acceleration

When dp[i] depends on the maximum value among dp[i-k] ... dp[i-1]:

Naive DP:      Scan K elements per step → O(N × K) time
MQ Optimized:  Monotonic Queue maintains max DP state in last K steps at Front → O(N) total time!

Featured Problems: Jump Game VI, Constrained Subsequence Sum

Visual Memory Rule

Front  →  removes EXPIRED values (outside window left)
Back   →  removes WEAKER values than current (while curr >= back)
Max    →  decreasing queue (Front = Max)
Min    →  increasing queue (Front = Min)

💡 Golden Rule: "Front removes values that are too old; back removes values that are too weak."

Common Interview Mistakes

1. Storing Only Values

Storing values prevents checking whether the front item is outside the window (deque[0] <= i - k). Store indexes!

2. Wrong Queue Monotonic Direction

Window Maximum requires a decreasing queue. Window Minimum requires an increasing queue.

3. Popping Only One Value with IF

One new larger value can make multiple older values useless. Always pop from back using a while loop!

4. Confusing Stack and Queue

Nearest next/prev greater element → Monotonic Stack. Window maximum/minimum → Monotonic Queue.

Interview Rules

1. Window maximum? → Decreasing Monotonic Queue
2. Window minimum? → Increasing Monotonic Queue
3. Expired element? → Remove from Front (deque[0] <= i - k)
4. Weaker than current? → Remove from Back (while curr >= back)
5. Store indexes on queue to easily check window expiration
6. Front always gives the current max or min answer
7. Best value among last K DP states? → Use Monotonic Queue DP optimization
8. Overall Complexity → O(n) time, O(k) space

Small Rules

Rule 1: For maximum, keep queue decreasing; Front is maximum.
Rule 2: For minimum, keep queue increasing; Front is minimum.
Rule 3: Store indexes so you can tell if an element is outside the window.
Rule 4: Each element is added once and removed once, so total work is O(n).
Rule 5: Nested `while` inside a `for` loop is still O(n) total time.

Production Thinking

CPU Usage Monitoring → Maintain peak CPU usage over last 5 minutes without repeated full scans

Request Latency Spikes → Highest latency among last 1000 requests in O(1) time per event

Sensor Data Stream → Minimum temperature reading in rolling 60-second window

Rate & Throughput Peak → Peak requests per second inside a sliding time window

Remember This

Window Max                 → Decreasing Queue
Window Min                 → Increasing Queue
Expired                    → Pop Front
Weaker than Current        → Pop Back
Current                    → Push Back
Answer                     → Front
Need position              → Store Index
Total                      → O(n)

💡 Golden Rule: "Front removes values that are too old; back removes values that are too weak."