Stage 1 · Code
Stacks & Queues
Monotonic Queue
Sliding window maximum with deque in O(n).
7 min readMastering Data Structures & Algorithms for Software Engineering InterviewsCode
Monotonic Queue Concept
A monotonic queue is a deque that maintains elements in sorted order. Used for sliding window problems where we need min/max of current window. Elements pushed at back, expired removed from front, monotonicity maintained by popping from back.
Implementation Template
Gomonotonic-queue-for-sliding-window-max.go
50 linesLn 1, Col 1Go
Queue stores (index, value) pairs. Push maintains decreasing order by popping smaller from back. Pop removes expired from front. Max is always at front. Each element enters/exits once → O(n).
Applications
- Sliding window maximum/minimum: O(n) for each.
- Shortest subarray with sum ≥ K: Monotonic queue on prefix sums.
- Constrained subsequence sum: DP + monotonic queue.
- Jump game variants: Min jumps with window constraints.
Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.