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 MaximumMonotonic decreasing index dequehard
- 2.Design Circular DequeFixed array buffer with front/rear indices & modulo %medium
- 3.Shortest Subarray with Sum at Least KPrefix Sum + Monotonic Dequehard
- 4.Jump Game VIDP + Monotonic Deque max window scoremedium
- 5.Constrained Subsequence SumDP + Monotonic Deque max window sumhard
- 6.Longest Continuous Subarray With Absolute Diff Less Than or Equal to LimitTwo Deques (maxDeque & minDeque)medium
- 7.Max Value of EquationMonotonic Deque storing (y_i - x_i, x_i)hard
- 8.Reveal Cards In Increasing OrderDeque card ordering simulationmedium
- 9.Dota2 SenateRadiant and Dire senator indices in Dequemedium
- 10.0-1 BFS ProblemsCost 0 -> Push Front, Cost 1 -> Push Backmedium
Also Important
7 more questions worth practicing.
- 11.Moving Average from Data StreamFixed window size queue/dequeeasy
- 12.First Negative Integer in Every WindowDeque storing negative element indicesmedium
- 13.Maximum of All Subarrays of Size KMonotonic decreasing index dequemedium
- 14.Find the Most Competitive SubsequenceMonotonic stack / deque of length Kmedium
- 15.Continuous SubarraysTwo Deques tracking window max and min diff <= 2medium
- 16.Minimum Number of K Consecutive Bit FlipsDeque / queue flip state bufferhard
- 17.Front Middle Back QueueTwo 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)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
For sliding window problems, storing values prevents checking window expiration (deque[0] < i - k + 1). Store indexes!
One new large value can invalidate multiple smaller elements in the deque. Always use a while loop!
Even if deque ordering is valid, front element might belong to a previous expired window. Check front boundary first!
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."