Monotonic Stack and Queue Pattern
The Idea
A monotonic stack is an ordinary stack with one rule: its contents stay sorted (all increasing or all decreasing from bottom to top). Before pushing a new element, you pop everything that would break the order — and the moment an element is popped is the moment its answer becomes known.
prices: 31 28 35 ... push 31 stack [31] push 28 (28 < 31, ok) stack [31, 28] 35 arrives: 35 > 28 → pop 28 ← 28's next higher price is 35 35 > 31 → pop 31 ← 31's next higher price is 35 push 35 stack [35] The stack holds exactly the elements still WAITING for an answer.
The Monotonic Stack page covers the data structure in depth. This page is a pattern guide: which order to keep, what a pop means, and when you need a deque instead.
Choosing the Order
QUESTION FOR EACH ELEMENT KEEP THE STACK POP WHEN NEW VALUE IS ───────────────────────────────── ──────────────── ───────────────────── next GREATER to the right decreasing greater than top next SMALLER to the right increasing smaller than top previous greater to the left decreasing (read the top after popping previous smaller to the left increasing ≤ / ≥ values — it's the answer) Mnemonic: the stack keeps the elements that have NOT yet met the thing they are looking for.
Strict vs non-strict (< vs <=) decides how equal values are treated — "strictly higher" pops only on >; "higher or equal" pops on >=.
Example 1: Days Until a Higher Price
prices: [31, 28, 35, 33, 30, 36, 29]
index: 0 1 2 3 4 5 6
i=0 31 stack [0]
i=1 28 stack [0, 1]
i=2 35 pop 1 (28) → wait[1] = 2−1 = 1
pop 0 (31) → wait[0] = 2−0 = 2 stack [2]
i=3 33 stack [2, 3]
i=4 30 stack [2, 3, 4]
i=5 36 pop 4 → wait[4] = 1, pop 3 → wait[3] = 2, pop 2 → wait[2] = 3
stack [5]
i=6 29 stack [5, 6]
end: indices 5 and 6 never found a higher price → wait = 0
wait: [2, 1, 3, 2, 1, 0, 0]
Example 2: Largest Rectangle Under a Skyline
Bars of width 1 with given heights. Find the largest rectangle that fits entirely under the skyline.
heights: [2, 4, 3, 5, 1, 3]
For each bar, the widest rectangle of exactly its height extends
left and right until a LOWER bar. Keep an INCREASING stack:
when a lower bar arrives, the popped bar's right limit is the new bar,
and its left limit is the bar below it in the stack.
height 5: . . . █ . .
height 4: . █ . █ . .
height 3: . █ ▓ █ . █
height 2: █ █ ▓ █ . █
height 1: █ █ ▓ █ █ █
index: 0 1 2 3 4 5
(▓ column + its neighbours at height ≤ 3 → the 3 × 3 rectangle over bars 1..3)
i=2 (3) pops 1 (height 4): left limit 0 → width 2−0−1 = 1 → area 4
i=4 (1) pops 3 (5): width 1 → 5
pops 2 (3): left limit index 0 → width 4−0−1 = 3 → area 9 ★
pops 0 (2): no left limit → width 4 → 8
end (sentinel 0) pops the rest: 3 × 1, 1 × 6 = 6
best = 9 (height 3 across bars 1..3)
A sentinel height 0 after the last bar flushes the stack so every bar gets processed.
Example 3: Maximum of Every Window (Monotonic Deque)
readings: [4, 2, 12, 3, 8, 7, 1, 6], k = 3
deque of INDICES with DECREASING values (front = current max):
i=0 4 dq [4]
i=1 2 dq [4, 2]
i=2 12 pop 2, pop 4 → dq [12] window [4,2,12] max 12
i=3 3 dq [12, 3] window [2,12,3] max 12
i=4 8 pop 3 → dq [12, 8] window [12,3,8] max 12
i=5 7 dq [12, 8, 7]; 12's index 2 ≤ 5−3 → drop front
dq [8, 7] window [3,8,7] max 8
i=6 1 dq [8, 7, 1] window [8,7,1] max 8
i=7 6 pop 1 → dq [8, 7, 6]; 8's index 4 ≤ 4 → drop front
dq [7, 6] window [7,1,6] max 7
maxima: [12, 12, 12, 8, 8, 7]
A value smaller than a newer value can never be a window maximum again (the newer one stays in the window longer), so it's safe to discard from the back.
Code: Next Higher, Largest Rectangle, Window Maximum
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;
public class MonotonicPatterns {
// 1. Days until a strictly higher price (0 if never) — decreasing stack of indices
static int[] daysUntilHigher(int[] prices) {
int[] wait = new int[prices.length];
Deque<Integer> stack = new ArrayDeque<>(); // indices still waiting
for (int i = 0; i < prices.length; i++) {
while (!stack.isEmpty() && prices[stack.peek()] < prices[i]) {
int j = stack.pop(); // prices[i] answers j
wait[j] = i - j;
}
stack.push(i);
}
return wait;
}
// 2. Largest rectangle under a skyline — increasing stack of indices
static int largestRectangle(int[] heights) {
Deque<Integer> stack = new ArrayDeque<>();
int best = 0;
for (int i = 0; i <= heights.length; i++) {
int h = (i < heights.length) ? heights[i] : 0; // sentinel 0 flushes the stack
while (!stack.isEmpty() && heights[stack.peek()] >= h) {
int top = stack.pop();
int left = stack.isEmpty() ? 0 : stack.peek() + 1;
best = Math.max(best, heights[top] * (i - left));
}
stack.push(i);
}
return best;
}
// 3. Maximum of every window of size k — decreasing deque of indices
static List<Integer> windowMaxima(int[] values, int k) {
Deque<Integer> dq = new ArrayDeque<>();
List<Integer> out = new ArrayList<>();
for (int i = 0; i < values.length; i++) {
while (!dq.isEmpty() && values[dq.peekLast()] <= values[i]) dq.pollLast(); // never a max again
dq.offerLast(i);
if (dq.peekFirst() <= i - k) dq.pollFirst(); // fell out of window
if (i >= k - 1) out.add(values[dq.peekFirst()]);
}
return out;
}
public static void main(String[] args) {
int[] prices = {31, 28, 35, 33, 30, 36, 29};
System.out.println("days until higher: " + Arrays.toString(daysUntilHigher(prices)));
for (int[] skyline : new int[][]{{2, 4, 3, 5, 1, 3}, {6, 6, 6}, {1, 2, 3, 4, 5}})
System.out.println("largest rectangle in " + Arrays.toString(skyline) + ": " + largestRectangle(skyline));
int[] readings = {4, 2, 12, 3, 8, 7, 1, 6};
System.out.println("window maxima (k=3): " + windowMaxima(readings, 3));
}
}Output:
days until higher: [2, 1, 3, 2, 1, 0, 0]
largest rectangle in [2, 4, 3, 5, 1, 3]: 9
largest rectangle in [6, 6, 6]: 18
largest rectangle in [1, 2, 3, 4, 5]: 9
window maxima (k=3): [12, 12, 12, 8, 8, 7]
Why It's O(n): Amortised Analysis
Don't count work per loop iteration — count it per ELEMENT: each index is PUSHED exactly once each index is POPPED at most once total stack operations ≤ 2n → O(n) time stack / deque size ≤ n → O(n) space A single iteration may pop many elements, but those elements can never be popped again — the cost is "paid in advance".
How to Spot It
✓ "next greater / next smaller / previous greater / previous smaller" ✓ "how many days / steps until ..." something larger or smaller appears ✓ "for each element, how far does it extend before something smaller/larger" (spans, histogram rectangles, visible-people counts) ✓ "sum over all subarrays of the minimum (or maximum)" → each element's contribution = value × (left span) × (right span) ✓ "maximum / minimum of every window of size k" → monotonic DEQUE ✓ Brute force: "for each i, scan right until ..." → O(n²) → monotonic stack
Stack vs Deque vs Heap
| Question | Tool | Time |
|---|---|---|
| Next/previous greater or smaller | Monotonic stack | O(n) |
| Max/min of every fixed-size window | Monotonic deque | O(n) |
| Max/min of a window that also needs arbitrary deletions | Heap with lazy deletion | O(n log n) |
| k largest overall | Heap of size k | O(n log k) |
Common Mistakes
Storing values instead of indices. Distances ("days until") and window checks both need positions. Store indices and look values up.
Strict vs non-strict comparison. With duplicates, < vs <= changes which equal element "answers" another. For "strictly greater", pop on <; for histogram rectangles, popping on >= handles equal heights correctly.
Forgetting leftover elements. Elements still on the stack at the end never found an answer — leave them at the default (0 or −1) or flush them with a sentinel.
Checking the window front before pushing. In the deque, push the new index first, then drop a stale front; otherwise a window of size 1 can end up empty.
Using Array.shift() in JavaScript. It's O(n) per call and silently turns the deque solution into O(n·k). Use a head index (as above) or a real deque.
Interview Questions
Q: How do you compute, for every element, the distance to the previous smaller element?
Scan left to right with an increasing stack. Before pushing index i, pop every index whose value is ≥ a[i]. The index left on top (if any) is the previous smaller element; the distance is i minus that index (or i + 1 if the stack is empty). Then push i.
Q: Explain why the largest-rectangle algorithm finds the optimum.
The optimal rectangle's height equals some bar's height h, and it extends as far as possible on both sides until a lower bar. When that bar is popped, the current index is exactly its right limit and the new stack top is exactly its left limit, so the algorithm evaluates that rectangle. Every bar is popped once, so every candidate is checked.
Q: Why can a smaller value be discarded from the back of the window deque?
If an older value is ≤ a newer value, the newer value stays in the window at least as long as the older one. So whenever the older value is inside a window, the newer one is too and is at least as large — the older value can never be the maximum again.
Summary
- ›A monotonic stack keeps elements in sorted order; a pop means that element's answer is now known.
- ›Decreasing stack → next greater; increasing stack → next smaller (and spans / rectangles).
- ›A monotonic deque adds front removal for sliding-window max/min.
- ›Every element is pushed once and popped at most once → O(n) amortised.
- ›Store indices, mind strict vs non-strict comparisons, and flush leftovers.
You have now covered all ten core algorithmic patterns. Put them to work in the practice problems — and when a problem feels unfamiliar, revisit How to Identify Patterns.
To find, for each day, how long until a strictly higher price, which stack order do you keep?