Pattern #18

Deque

Important interview questions, thinking patterns, monotonic sliding window deques, 0-1 BFS, and rules for solving deque problems in Go.

Must Solve

10 core questions — solve these first.

1.Sliding Window Maximum
Monotonic decreasing index dequehard
2.Design Circular Deque
Fixed array buffer with front/rear indices & modulo %medium
3.Shortest Subarray with Sum at Least K
Prefix Sum + Monotonic Dequehard
4.Jump Game VI
DP + Monotonic Deque max window scoremedium
5.Constrained Subsequence Sum
DP + Monotonic Deque max window sumhard
6.Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit
Two Deques (maxDeque & minDeque)medium
7.Max Value of Equation
Monotonic Deque storing (y_i - x_i, x_i)hard
8.Reveal Cards In Increasing Order
Deque card ordering simulationmedium
9.Dota2 Senate
Radiant and Dire senator indices in Dequemedium
10.0-1 BFS Problems
Cost 0 -> Push Front, Cost 1 -> Push Backmedium

Also Important

7 more questions worth practicing.

11.Moving Average from Data Stream
Fixed window size queue/dequeeasy
12.First Negative Integer in Every Window
Deque storing negative element indicesmedium
13.Maximum of All Subarrays of Size K
Monotonic decreasing index dequemedium
14.Find the Most Competitive Subsequence
Monotonic stack / deque of length Kmedium
15.Continuous Subarrays
Two Deques tracking window max and min diff <= 2medium
16.Minimum Number of K Consecutive Bit Flips
Deque / queue flip state bufferhard
17.Front Middle Back Queue
Two Deques (left & right halves balanced)medium

How to Think

Need add/remove from both sides?Deque (Double-Ended Queue)
Need maximum/minimum in every window?Sliding Window + Monotonic Deque
Need remove old elements from front?Deque (Pop Front)
Need remove useless elements from back?Monotonic Deque (Pop Back)
Edges have only cost 0 or 1?0-1 BFS + Deque

Go Sliding Window Max Deque Template

Monotonic Deque Template in Go

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

for i := 0; i < len(nums); i++ {
    // 1. Remove expired elements from FRONT (outside window left: i - k + 1)
    if len(deque) > 0 && deque[0] < i-k+1 {
        deque = deque[1:]
    }

    // 2. Remove smaller useless candidates from BACK
    for len(deque) > 0 && nums[deque[len(deque)-1]] <= nums[i] {
        deque = deque[:len(deque)-1]
    }

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

    // 4. Front is max for current window once i >= k - 1
    if i >= k-1 {
        result = append(result, nums[deque[0]])
    }
}

👉 Total Time: O(n) | Space: O(k) (Each index is added once & removed once)

Sliding Window Maximum Mechanics

Why do we remove from the back when a new element arrives?

Suppose Deque contains: [8, 5, 3]
New value arrives:      6

3 & 5 are useless because 6 is LARGER and NEWER.
3 & 5 can never be the maximum in any future window containing 6!
Pop 3 & 5 from back → Deque becomes [8, 6].

💡 Golden Rule: "Smaller older values can never beat a newer bigger value."

0-1 BFS Graph Optimization

When graph edge weights are strictly 0 or 1, avoid full $O((V+E) \log V)$ Dijkstra! Use a Deque instead in $O(V+E)$:

Edge Cost = 0  →  Push to FRONT of Deque (process immediately)
Edge Cost = 1  →  Push to BACK of Deque (process standard queue sequence)

Visual Memory Rule

Front  →  removes EXPIRED items (outside left window boundary)
Back   →  removes USELESS smaller candidates
Max    →  decreasing monotonic deque (Front = Max)
Min    →  increasing monotonic deque (Front = Min)

💡 Golden Rule: "Front removes what is too old; back removes what is no longer useful."

Common Interview Mistakes

1. Storing Values Instead of Indexes

For sliding window problems, storing values prevents checking window expiration (deque[0] < i - k + 1). Store indexes!

2. Popping Only Once from Back

One new large value can invalidate multiple smaller elements in the deque. Always use a while loop!

3. Forgetting Expired Items

Even if deque ordering is valid, front element might belong to a previous expired window. Check front boundary first!

4. Wrong Monotonic Direction

For window maximum: keep deque decreasing. For window minimum: keep deque increasing.

Interview Rules

1. Need both ends? → Deque
2. Sliding Window Maximum? → Monotonic Deque
3. Sliding Window Minimum? → Monotonic Deque
4. Remove expired elements? → Pop from Front (deque[0] < leftBoundary)
5. Remove useless candidates? → Pop from Back (while curr >= back)
6. Window Max? → Decreasing deque
7. Window Min? → Increasing deque
8. 0-1 BFS? → Edge cost 0: Push Front, Edge cost 1: Push Back
9. Overall Complexity → O(n) time, O(k) space

Small Rules

Rule 1: All Deque operations (Push Front, Push Back, Pop Front, Pop Back) are O(1).
Rule 2: For Sliding Window problems, always store element indexes, not values.
Rule 3: Max window uses decreasing deque; Min window uses increasing deque.
Rule 4:Each element enters once & leaves once, making Monotonic Deque O(n) total time.
Rule 5: Deque is the data structure; Monotonic Deque is the ordered sliding window pattern.

Production Thinking

Sliding Metric Monitoring → Max CPU / memory usage in last 60 seconds window

Request Latency Tracking → Max API latency over rolling 5-minute window in O(1) per event

Bounded Event Buffers → Maintain recent incoming events with O(1) front eviction

Priority Task Schedulers → Urgent jobs pushed to Front, normal jobs to Back

Work Stealing Schedulers → Concurrent worker threads process local work from Front, steal from Back

Remember This

Both ends                  → Deque
Window maximum             → decreasing deque
Window minimum             → increasing deque
Expired element            → pop front
Useless candidate          → pop back
Current element            → push back
Answer                     → front
0-cost edge                → push front
1-cost edge                → push back

💡 Golden Rule: "Front removes what is too old; back removes what is no longer useful."