Queues & Deques
Queues process elements in arrival order. Deques extend this with front and back operations.
Lessons
1. Intro
The FIFO principle
2. Vocabulary - Queue
First in, first out
3. Queue Visualization
See it work
4. Queue Implementation
Array or linked list
5. Where Queues Shine
Common applications
6. BFS Overview
Level-order exploration
7. Problem - Number of Recent Calls
Simple queue problem
8. Recent Calls - Algorithm
Sliding time window
9. Recent Calls - Implementation
Complete solution
10. Lessons from Recent Calls
Queue as window
11. Quiz: Queue Basics
FIFO behavior
12. The Limitation of Queues
Single-ended access
13. Vocabulary - Deque
Double-ended queue
14. Deque Implementation
Built-in support
15. The Sliding Window Maximum
A classic problem
16. Vocabulary - Monotonic Deque
Ordered double-ended
17. Why Monotonic Deque Works
The core idea
18. Monotonic Deque Visualization
Step by step
19. Problem - Sliding Window Maximum
Classic deque problem
20. Sliding Max - Algorithm
Maintain monotonicity
21. Sliding Max - Implementation
Complete solution
22. Lessons from Sliding Max
Key patterns
23. Quiz: Monotonic Deque
Maintenance rules
24. Sliding Window Minimum
The mirror problem
25. A Harder Problem
Prefix sum + deque
26. Shortest Subarray - The Idea
Using prefix sums
27. Shortest Subarray - Algorithm
Two operations
28. Shortest Subarray - Implementation
Complete solution
29. Lessons from Shortest Subarray
Combined techniques
30. Quiz: Deque vs Stack vs Queue
Choosing structures
31. Deque vs Two Stacks
Alternative approach
32. When to Use Deques
Problem signals
33. Problem - Constrained Subsequence Sum
DP with deque
34. Constrained Sum - DP Formulation
State and transition
35. Constrained Sum - Implementation
DP with sliding max
36. Lessons from Constrained Sum
DP optimization
37. Quiz: DP Optimization
When deques help
38. Section Recap
What we learned
Practice Problems
Perfect introduction to queue simulation where students swap positions based on simple rules.
Excellent for understanding queue structure reconstruction from neighbor relationships.
Teaches deque operations with pattern recognition. Great for understanding how deques stabilize into cycles.
BFS tree traversal using queue with state tracking. Perfect for learning queue-based graph exploration.
Demonstrates how choosing front/back insertion affects final structure. Excellent for understanding inversion counts.
Teaches optimal removal from deque ends to achieve target sum. Great introduction to deque manipulation.
Advanced queue problem requiring finding furthest younger elements. Teaches monotonic stack/deque optimization.
Verifies if a sequence represents valid BFS traversal. Essential for understanding BFS queue mechanics.
BFS with priority queue to find lexicographically smallest path. Modified BFS with ordering requirements.
Classic monotonic deque DP optimization. Teaches how to use deque to optimize range maximum queries in DP.
Greedy problem with implicit queue of powers of two. Understanding bit manipulation with queue-like processing.
2D sliding window maximum using monotonic deque in both dimensions. Ultimate monotonic deque technique mastery.
Fundamental problem teaching queue FIFO principles by implementing with LIFO stacks. Amortized O(1) operations.
Teaches circular buffer concepts with wrap-around indexing using modulo arithmetic.
THE canonical monotonic deque problem. Reduces O(nk) to O(n) using decreasing deque for potential maxima.
Combines prefix sum with monotonic deque to handle negative numbers elegantly.
Classic DP optimization reducing O(nk) to O(n) using monotonic deque for sliding window maximum in DP.
DP disguised as sliding window maximum. Monotonic deque optimizes finding best previous jump position.
Advanced application using TWO monotonic deques (one for min, one for max) simultaneously.
Mathematical transformation combined with monotonic deque for variable-width sliding window optimization.