Monotonic deque
Overview
A combination of a Deque and the Monotonic concept. Elements inside the deque are kept in strictly increasing or decreasing order.
It allows O(1) amortized tracking of the minimum or maximum over a sliding window.
Where used: Stock market tick data analysis (moving max/min), Network packet buffer management
Why it exists
Problem: We want to find the maximum (or minimum) element in every sliding window of size `K` across an array. A Max Heap gives O(N log K), but we want O(N).
Naive approach: For each window of size K, scan the K elements to find the max. Total time O(N * K).
Better idea: Keep a Double-Ended Queue (Deque) that stores elements in strictly decreasing order. The maximum element of the window is always at the front, and we remove smaller useless elements from the back.
Why learn this
- It is the optimal, O(N) solution to the famous 'Sliding Window Maximum' interview question.
- It combines sliding window pointer management with monotonic stack logic.
Mental model
If a newer, taller candidate arrives in the window, all older, shorter candidates are instantly irrelevant—they can never be the maximum anymore. Fire them immediately.
We use a Deque to store array indices. When sliding the window, we first remove indices from the front that are out of the window bounds. Then, from the back, we remove indices whose array values are less than or equal to the incoming value. Finally, we push the incoming index to the back. The front of the deque is always the maximum for the current window.
Repeated decision: Is the guy at the back of the queue smaller than me? If yes, kick him out, because he's older than me AND smaller, so he'll never be the maximum of any future window.
Deep dive
The Monotonic Deque is a direct evolution of the Monotonic Stack. A Monotonic Stack is great for finding the 'Next Greater Element'. But a stack only lets you pop from the top. In a sliding window, elements expire from the *back* of the window, so we need to pop from both ends—hence, a Deque.
Suppose we want the maximum in a window of size `K`. We maintain a deque of indices. The values at these indices will be strictly decreasing.
For every new element `arr[i]`:
1. **Clean up expired elements:** If the index at the front of the deque is `<= i - K`, it has fallen out of our window. Pop it from the front.
2. **Maintain monotonicity:** While the deque is not empty and `arr[i]` is `>=` the element at the back of the deque, pop from the back. (Why? Because `arr[i]` is both newer AND larger. The smaller element can never be the maximum of any window from now on).
3. **Push:** Append `i` to the back.
4. **Report:** If our window has reached size `K`, the maximum is simply the element at the front of the deque.
Every element is pushed and popped at most once, making the algorithm strictly `O(N)`.
Key points
- Complexity: Time is O(N) overall (O(1) amortized per element). Space is O(K) for the deque.
- Store Indices: Always store array INDICES in the deque, not values. You need the index to determine if an element has fallen out of the sliding window boundary.
Pattern: Monotonic Deque
Recognition cues:
- Sliding Window Maximum
- Find min/max in every contiguous subarray of size K
Failure signals
- The problem asks for something other than a strict monotonic property (like median or average).
Engineering examples
Real-time Metrics
Tracking the highest latency request in the last 5 minutes.
A monotonic deque can maintain this rolling maximum efficiently without recalculating.
When not to use
- When you need the median or sum: A Monotonic Deque only works for Min or Max queries where elements can totally dominate others. For sliding sums, use Prefix Sums. For sliding medians, use two Heaps.
Common mistakes
- Storing values instead of indices: If you just store the value `5` in the deque, you won't know when that `5` has expired out of the window's left edge.
- Popping from the wrong side: Expired items are popped from the FRONT (the oldest end). Monotonic maintenance (kicking out smaller items) happens at the BACK (the newest end).
Recall questions
- Why must you store indices in a Monotonic Deque instead of the actual array values?
- What is the time complexity of Sliding Window Maximum using a Monotonic Deque?
Understanding checks
When building a 'Sliding Window Maximum' deque, you encounter a new element that is smaller than the back of the deque. Do you kick out the back of the deque?
No. You just append the new element.
The new element is smaller, but it is newer. When the larger elements expire and leave the window, this smaller element might become the new maximum.
If your window size is 3 and your array is `[5, 4, 3, 2, 1]`, what does the deque do?
It never kicks anything out for being too small. It only kicks out elements from the front as they expire.
The array is strictly decreasing, so every new element is smaller than the back of the deque. The deque just stores the window elements.
Questions & answers
Sliding Window Maximum
The canonical problem. Use a deque to keep a decreasing monotonic sequence of indices.
Approach: Clean expired indices from front, pop smaller values from back, append current index, read front.
Practice tasks
Sliding Window Maximum
You are given an array of integers `nums`, there is a sliding window of size `k` which is moving from the very left of the array to the very right. Return the max sliding window.
Continue learning
Previous: Queue & deque
Previous: Monotonic stack
Previous: Sliding window (fixed)