·
Keep a stack (or deque) whose values stay sorted. When the incoming element violates that order, pop — and every pop resolves an answer: a next greater/smaller element, a bounding wall for a rectangle, a merged car fleet, a window maximum. Because each element is pushed and popped at most once, the whole sweep is O(n) amortized. The same idea reaches across Stack, Two Pointers, and Sliding Window problems.
Keep the stack sorted. The moment a new element would break that order, the elements it breaks are exactly the ones it answers — so pop them, record their result, and push the newcomer to wait for its own. One sorted pile, one pop per resolved element, O(n) total.
Picture a stack where every element is still waiting for something — the next taller bar, a shorter wall, a faster car. You keep the pile sorted (decreasing or increasing), so the only element that can ever be resolved next is sitting right on top. When a new element arrives that violates the order, it is precisely the answer for the elements it violates: pop each one, hand it its result, and stop when the order holds again.
That single discipline unifies problems that look unrelated:
Brute force re-reads the right side for every element — the same cells over and over:
Brute force: "next greater to the right" → for each i, scan right
nums = [ 2 1 3 ]
i=0 (2): look right → 1? no … → 3? yes ◄ rescanned 1 then 3
i=1 (1): look right → 3? yes ◄ rescanned 3 again
i=2 (3): look right → (nothing)
~n²/2 comparisons, the same cells re-read.
The waste IS re-reading the right side for every element.The monotonic stack keeps only the elements still waiting, in sorted order. When 3 arrives on [2, 1, 3] it cascades — popping the 1 then the 2, each pop resolving one waiting element:
nums = [ 2, 1, 3 ] stack holds indices WAITING for a bigger value
(values strictly DECREASING bottom→top)
i=0 val 2 stack empty, push stack(vals): [ 2 ]
i=1 val 1 1 < 2, push stack(vals): [ 2, 1 ]
i=2 val 3 3 > 1 → pop 1, ans[1] = 3 stack(vals): [ 2 ]
3 > 2 → pop 2, ans[0] = 3 stack(vals): [ ]
push 3 stack(vals): [ 3 ]
leftover: 3 has nobody bigger to its right → ans[2] = -1
result: [ 3, 3, -1 ]
The arriving 3 "beats" everything it towers over and pops them.
Each popped element just found its next-greater answer — and each
index is pushed once, popped once → O(n) despite the inner loop.while looks nested, but each index is pushed once and popped once across the whole run. Total pops ≤ total pushes = n. The nesting is an illusion.For a sliding window maximum the sorted pile needs one extra move: the current max can age out of the window before any bigger value beats it, so you also drop stale indices off the front. That two-ended pruning is the only difference between a monotonic stack and a monotonic deque:
Sliding-window max, k = 3: nums = [ 1 3 -1 -3 5 ]
idx 0 1 2 3 4
deque stores INDICES; values decrease front→back; FRONT = window max.
r=0 push 0 dq(vals): [ 1 ]
r=1 3 ≥ 1 pop back, push 1 dq(vals): [ 3 ] ← 1 was dominated
r=2 -1 < 3 push 2 dq(vals): [ 3, -1 ] window full → max = 3
r=3 -3 push 3 dq(vals): [ 3, -1, -3 ] win [3,-1,-3] → max = 3
r=4 front idx 1 ≤ 4-3 → shift; 5 pops -3,-1,3, push 4
dq(vals): [ 5 ] win [-1,-3,5] → max = 5
result: [ 3, 3, 5 ]
Stack pops from ONE end. A deque also drops STALE indices off the
FRONT, because the max can age out of the window before it's beaten.When you suspect a monotonic structure, climb these rungs in order:
i − j distance or a span width on a pop; recover the value with nums[index].-1), or a sentinel flushes it (histogram's trailing 0).Before coding, say in one sentence what each item on the stack is waiting for. Finish that sentence and the logic writes itself:
Strip away the problem and every monotonic-stack solution is the same three moves: pop everyone the newcomer beats (they just found their answer) → record it → push the newcomer to wait for its own:
for each index i, left to right:
while stack not empty AND nums[i] beats nums[stack.top]:
j = stack.pop() # j was WAITING — i is its answer
record answer for j # a value, a distance i - j, or an area
push i # i now waits for ITS own answer
# anything still on the stack never found an answer → default (-1)The monotonic-deque adds one rung — expire the front when the window slides past it — so the front is always the live window extreme:
for each index right, left to right:
if front index has aged out of the window:
pop it off the FRONT
while back value is dominated by nums[right]:
pop it off the BACK # it can never be the max again
push right onto the back
once the window is full:
emit nums[front] # the running max/minThe onlythings that change between problems are the “beats” comparison (> vs <, strict vs non-strict for duplicates) and what you record on a pop (a value, a distance, an area). The shape never changes.
A monotonic stack maintains its elements in sorted order (strictly increasing or decreasing). You scan once; for each new element you pop everything that violates the order, and every pop is a resolved answer. Then you push the newcomer so it waits for its resolution. The four classic shapes:
The reason this pattern is so powerful is that a pop and an answer are the same event. You never search for an element's neighbor; you wait, and when the neighbor arrives it pops you. The stack is a queue of unresolved obligations, kept sorted so the next resolvable one is always on top.
Push the index, not the value — that way a pop can compute a distance (i − j) or a span width, and you recover the value with nums[index].
The inner while loop can pop at most n elements across the entire outer loop — total pops are bounded by total pushes, which is exactly n. The deque variant is identical: every index enters and leaves each end at most once.
The mental model is the same sorted pile; the deque just adds front-eviction so a bounded window never reports a stale extreme.
1function nextGreater(nums: number[]): number[] {2 const n = nums.length;3▶ const res = new Array<number>(n).fill(-1);4▶ const stack: number[] = []; // indices; values decreasing top→bottom5▶6 for (let i = 0; i < n; i++) {7 // current value beats everything it towers over → resolve them8 while (stack.length && nums[i] > nums[stack[stack.length - 1]]) {9 const j = stack.pop()!; // j was WAITING; i is its answer10 res[j] = nums[i];11 }12 stack.push(i); // i now waits for ITS next-greater13 }14 return res; // leftover indices keep -115}
Reach for a monotonic structure when you need the nearest element that is greater or smaller, a span bounded by walls, or the extreme of a moving window. The tell is that each element is “waiting” for some future element that resolves it — and that future element arrives in scan order.
| "next greater / next smaller element", "next warmer day" | monotonic stack of indices; pop when the newcomer violates the order, that pop is the answer |
| "previous smaller / nearest smaller to the left" | monotonic increasing stack; the answer is the new top after popping (or scan right-to-left) |
| "largest rectangle / maximum span bounded by taller (or shorter) bars" | monotonic stack of indices; the popped bar’s width = i − new-top − 1 |
| "trapping rain water" — water bounded by walls on both sides | monotonic decreasing stack of indices; each pop is a horizontal layer of trapped water |
| "merge / collapse by who catches up" (car fleet, asteroid collision) | sort or scan in arrival order; a dominating newcomer pops (absorbs) the element ahead |
| "max / min of every window of size k" | monotonic deque of indices; pop dominated off the back, expire stale off the front, front = extreme |
When → The problem asks for the next (or previous) element that is greater, or the distance to it. Keep a decreasing stack of indices; pop while the newcomer exceeds the top, recording each popped element's answer.
// Monotonic DECREASING stack → next greater element to the right, in O(n).
// The stack holds INDICES whose values decrease bottom→top: each one is
// "waiting" for a value bigger than it to show up on its right.
function nextGreater(nums: number[]): number[] {
const n = nums.length;
const res = new Array<number>(n).fill(-1);
const stack: number[] = []; // indices, values decreasing top→bottom
for (let i = 0; i < n; i++) {
// Every value the newcomer towers over has just found its answer → pop them.
while (stack.length && nums[i] > nums[stack[stack.length - 1]]) {
const j = stack.pop()!; // j was waiting; i is its next-greater
res[j] = nums[i]; // record the ANSWER (or i - j for distance)
}
stack.push(i); // push the INDEX, not the value
}
return res; // leftover indices have no greater → stay -1
}i − stack.pop() (a distance), which is impossible if the stack only holds values. Recover the value with nums[index] when comparing.When → You compute a max area or span bounded by a shorter element on either side (Largest Rectangle, Maximal Rectangle per row). Append a sentinel 0 so the final loop iteration flushes every remaining bar.
// Largest rectangle in a histogram — monotonic INCREASING stack of bar indices.
// When a shorter bar arrives it is the right wall for every taller bar still on
// the stack; each pop fixes that bar's full max-width rectangle.
function largestRectangle(heights: number[]): number {
const bars = [...heights, 0]; // sentinel 0 flushes every remaining bar
const stack: number[] = []; // increasing stack of indices
let best = 0;
for (let i = 0; i < bars.length; i++) {
while (stack.length && bars[i] < bars[stack[stack.length - 1]]) {
const h = bars[stack.pop()!]; // the popped bar's height
// Left wall = the new top (exclusive); right wall = i (exclusive).
const w = stack.length ? i - stack[stack.length - 1] - 1 : i;
best = Math.max(best, h * w);
}
stack.push(i);
}
return best;
}j, the left wall is the new stack top (exclusive) and the right wall is i (exclusive), so w = i − newTop − 1. If the stack is empty after the pop, j is the shortest bar so far and w = i.When → You need the maximum (or minimum) of every fixed-size window in O(1) per step. A decreasing deque of indices keeps the front as the window max; expire stale front indices and pop dominated back values before each push.
// Maximum of every window of size k — monotonic DECREASING deque of indices.
// The deque is pruned from BOTH ends: the front drops stale (out-of-window)
// indices; the back drops values the newcomer dominates. Front is always the max.
function slidingWindowMaximum(nums: number[], k: number): number[] {
const res: number[] = [];
const dq: number[] = []; // indices; nums[dq] decreasing front→back
for (let right = 0; right < nums.length; right++) {
// 1. Evict the front if it has slid out of the window.
if (dq.length && dq[0] <= right - k) dq.shift();
// 2. Drop dominated values off the BACK before pushing the newcomer.
while (dq.length && nums[dq[dq.length - 1]] <= nums[right]) dq.pop();
dq.push(right);
// 3. Once the first full window is formed, the front index is the max.
if (right >= k - 1) res.push(nums[dq[0]]);
}
return res;
}dq[0] ≤ right − k) is what makes it a deque rather than a stack — the max can leave the window before any larger value beats it. Store indices so you can detect that expiry.Most monotonic problems need the index on the stack/deque, not the value. On a pop you typically want a distance (i − j), a span width, or — for the deque — to test whether the front has slid out of the window. Storing only the value makes all three impossible. Recover the value with nums[index] during comparison.
Whether you use > vs >= (and < vs <=) in the “pop while” condition decides what happens with equal elements. >= pops duplicates eagerly so only the rightmost duplicate records an answer; > keeps duplicates so each answers independently. In Sliding Window Maximum, popping equal values off the back (<=) is fine because the later index is the one that stays in the window longer. Read “strictly greater” vs “greater or equal” in the statement carefully.
After the main loop, elements still on a monotonic stack have no resolving element — their answer is the default (-1, or 0 for some problems). Histogram-style code sidesteps this by appending a sentinel that forces a final flush; without it, the tallest bars never get their rectangle. A common bug is returning before draining.
A monotonic deque is not just a stack — you must also drop indices that have aged out of the window off the front (dq[0] ≤ right − k). Omit that and the front can report a maximum that is no longer inside the window. Pop dominated values off the back, expire stale indices off the front, then read the front.
i arrives, pop every cooler day j and set answer[j] = i − j. This is the move every other problem here generalizes.#84Largest Rectangle in HistogramThe span / wall move.A shorter bar is the right wall for every taller bar on the stack; each pop fixes that bar's rectangle with width = i − newTop − 1. Append a sentinel 0 to drain the stack cleanly.#85Maximal RectangleHistogram, applied per row. Reduce the 2-D grid to a heights array per row (running column counts of 1s), then run the largest-rectangle stack on each row. Drills reusing the span move inside an outer sweep.#853Car FleetThe merge-by-domination move. Sort cars by start position descending and walk a stack of arrival times: a car that arrives no later than the fleet ahead is popped (it merges in). The remaining stack height is the fleet count — the pop is the merge.#32Longest Valid ParenthesesStack of indices as boundary markers. Push -1 as a base, push ( indices, and on ) pop then measure i − stack.top. Drills using the stack top as the left boundary of the current valid run — the same “new top is the wall” idea as the histogram.#42Trapping Rain WaterCross-category reach: a Two Pointers problem. The monotonic-stack solution keeps a decreasing stack of indices; when a taller bar arrives, each pop is a horizontal layer of water bounded by the new top (left wall) and the newcomer (right wall). Shows the same wall-bounding logic outside the Stack category (the two-pointer solution is the other route).#239Sliding Window MaximumCross-category reach: a Sliding Window problem, solved with the deque variant. Pop dominated values off the back, expire indices that slid past the window off the front, and the front index is the window max. This is where the technique steps beyond the single-ended stack into a two-ended deque.