Monotonic Stack

Any time you catch yourself writing a nested loop to find “the next bigger value to the right” or “how far until something taller shows up”, stop — there’s a one-pass, $O(n)$ trick for it. A monotonic stack keeps only the indices that could still matter, discarding the rest the instant a new element proves them irrelevant.

What you’ll learn

• The cue: “next greater element”, “next smaller element”, “days until warmer”, or anything about comparing each element to what comes after it.
• The template: a stack of indices that stays increasing (or decreasing) in value, popped whenever the incoming element breaks that order.
• Why every index is pushed and popped at most once, giving $O(n)$ total despite the while loop inside the for loop.
• How the same idea extends to histogram-area and rainwater-trapping problems.

The pattern: a decreasing stack for “next greater”

Keep a stack of indices, where the corresponding values are always decreasing from bottom to top. When a new value arrives that’s bigger than the value at the top of the stack, that new value is the “next greater element” for everything it pops — so pop them all, recording the answer for each, before pushing the new index.

next_greater_element.py

def next_greater_elements(nums):
    n = len(nums)
    result = [-1] * n     # default: no greater element exists
    stack = []             # indices, values decreasing bottom-to-top
 
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            result[stack.pop()] = x     # x is the next greater element for this popped index
        stack.append(i)
 
    return result
 
 
nums = [2, 1, 2, 4, 3]
print(next_greater_elements(nums))   # expect [4, 2, 4, -1, -1]

Every index enters the stack exactly once (one append per loop iteration) and leaves it at most once (one pop total, ever, per index) — so despite the nested while, the total work across the whole function is $O(n)$, not $O(n^2)$.

The cue

You are looking at a monotonic stack when…

• The problem asks, for every element, about the next (or previous) element that is greater or smaller than it. “Days until a warmer temperature”, “next greater element”, “how far until a taller building”.
• Or it asks for the largest rectangle / span bounded by a smaller value on each side — the same question wearing a different hat.
• Or a value’s answer becomes knowable only when a later value arrives, so entries must wait in order.

The stack holds indices whose answer is still unknown, kept sorted by value. When a new element arrives it resolves every waiting entry it beats, and those entries are then gone for good — which is the whole reason the nested loop is still linear.

Reach for something else when the query is about a window rather than a comparison (that is a monotonic deque, which supports eviction from both ends), or when you need the k-th largest rather than the next larger (a heap).

Visual intuition

Watch the pop counter. The while loop inside the for loop looks quadratic and is not — every index is pushed once and popped at most once across the entire run:

stackThe stack holds every index still waiting for an answerLC 739 · O(n) amortised

730741752713694725766737

days to wait

········

stack (top)

empty

bottom

stack0total pops0

1def daily_temperatures(temps):2    out = [0] * len(temps)3    stack = []                      # indices, temps DECREASING upward4    for i, t in enumerate(temps):5        while stack and temps[stack[-1]] < t:6            j = stack.pop()         # t is j's answer7            out[j] = i - j8        stack.append(i)9    return out                      # anything left has no answer

setupThe stack holds **indices whose answer is still unknown**, and it is kept decreasing in temperature from bottom to top. That invariant is the whole pattern: a value can only resolve the entries above it, never below.

Play‹›1/24⟲

The stack is kept decreasing from bottom to top. That invariant is what guarantees a value can only ever resolve entries above it, so nothing is examined twice.

How it works

sketch A decreasing monotonic stack scanning [2, 1, 2, 4, 3] p5.js Pause Restart

Each bar's index is pushed onto the stack. A new, taller bar pops every shorter bar still on the stack -- each pop resolves that index's 'next greater element'.

Worked example: Daily Temperatures

“How many days until a warmer temperature?” is the exact same pattern with the answer reframed as a distance (i - j) instead of the popped value itself.

daily_temperatures.py

def daily_temperatures(temperatures):
    n = len(temperatures)
    result = [0] * n       # default: no warmer day ever comes
    stack = []              # indices, temperatures decreasing bottom-to-top
 
    for i, t in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < t:
            j = stack.pop()
            result[j] = i - j     # how many days until it got warmer
        stack.append(i)
 
    return result
 
 
temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(daily_temperatures(temps))   # expect [1, 1, 4, 2, 1, 1, 0, 0]

Extending it: increasing stack for histogram area

Flip the invariant to an increasing stack (indices with values increasing bottom-to-top) and you get the classic Largest Rectangle in Histogram: when a bar shorter than the stack’s top arrives, that bar caps how far every taller bar above it could have stretched, so pop and price each one out.

largest_rectangle_histogram.py

def largest_rectangle_area(heights):
    stack = []       # indices, heights increasing bottom-to-top
    max_area = 0
 
    for i, h in enumerate(heights + [0]):   # sentinel 0 flushes the stack at the end
        while stack and heights[stack[-1]] >= h:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)
 
    return max_area
 
 
print(largest_rectangle_area([2, 1, 5, 6, 2, 3]))   # expect 10

Trapping Rain Water can be solved the same way too: a decreasing stack of indices, where popping a “valley” bar lets you compute the water trapped above it, bounded by the shorter of its left and right walls.

Increasing vs. decreasing — pick based on what “breaks” the invariant

Use a decreasing stack when a bigger incoming value is the interesting event (next greater element, warmer day). Use an increasing stack when a smaller incoming value is the interesting event (histogram area, where a short bar caps every taller bar’s reach). The direction always matches whichever comparison triggers your pops.

Time and space complexity

Operation	Complexity
Next greater/smaller element, one pass	$O(n)$ time — each index pushed and popped once
Daily Temperatures	$O(n)$ time
Largest Rectangle in Histogram	$O(n)$ time
Space (the stack itself)	$O(n)$ worst case

When to use it

• The question is phrased as “next greater/smaller element” or “distance until a bigger/smaller value appears” — a brute-force nested loop is $O(n^2)$, a monotonic stack is $O(n)$.
• You’re computing areas or bounded regions defined by heights — histogram bars, skyline problems, rainwater trapped between bars — where each bar’s contribution depends on the nearest taller bar on each side.
• You need, for every index, the nearest index to the left or right that breaks some ordering — the stack always holds exactly the candidates that haven’t been “resolved” yet.

Practice — real LeetCode problems

Each exercise is the actual LeetCode problem with its real method signature and LeetCode’s own examples as the test. Write the body, press Run, and match the expected output — then paste the same code into leetcode.com.

LC 496 — Next Greater Element I · Easy

Problem. nums1 is a subset of nums2. For each value in nums1, find the next greater element to its right in nums2, or -1 if none exists.

Constraints. 1 <= len(nums1) <= len(nums2) <= 1000, all values unique within each array.

Examples. nums1 = [4,1,2], nums2 = [1,3,4,2] gives [-1,3,-1] · nums1 = [2,4], nums2 = [1,2,3,4] gives [3,-1]

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Maintain a stack of values still waiting for a greater element, kept decreasing. A new value resolves every smaller value on the stack at once, because it is the first greater element for all of them.

Time $O(n + m)$ — each value is pushed once and popped at most once. Space $O(n)$.

Values still on the stack at the end never found anything greater, which is exactly what nxt.get(n, -1) expresses — no explicit flush needed.

Keying by value works only because the problem guarantees uniqueness. With duplicates you must key by index, which is what LC 739 does.

Follow-ups you should expect: “Circular array (LC 503)?” — iterate twice over the array (or over nums * 2) so later elements can wrap around, pushing only on the first pass. “Duplicates allowed?” — store indices instead of values. “Next smaller element?” — flip the comparison to an increasing stack. “Previous greater element?” — sweep right to left.

LC 739 — Daily Temperatures · Medium

Problem. Given daily temperatures, return an array where answer[i] is the number of days you must wait after day i for a warmer temperature. If no warmer day exists, put 0.

Constraints. 1 <= len(temperatures) <= 10^5, 30 <= temperatures[i] <= 100.

Examples. [73,74,75,71,69,72,76,73] gives [1,1,4,2,1,1,0,0] · [30,40,50,60] gives [1,1,1,0] · [30,60,90] gives [1,1,0]

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Exactly LC 496’s sweep, with two adaptations: the stack holds indices so the answer can be a distance, and the output is pre-filled with 0 so days that never find a warmer one need no special handling.

Time $O(n)$ — each index pushed once, popped at most once. Space $O(n)$.

The reason this beats the $O(n^2)$ nested scan is that a colder day sitting under a warmer one on the stack can never be the answer for anything to the right — the warmer day would resolve it first. So each index only needs to be considered once.

Because temperatures may repeat, the comparison is strict (< t): an equal temperature is not warmer, so it must not resolve the day beneath it. That is why indices rather than values are needed here where LC 496 could use values.

Follow-ups you should expect: “Do it right to left instead?” — also works, and you can skip forward using already-computed answers. “Previous warmer day?” — sweep in the other direction. ”$O(1)$ space?” — not possible in general; you must remember unresolved days. “Why does the stack stay decreasing?” — anything that would break the order is popped first, by construction.

LC 84 — Largest Rectangle in Histogram · Hard

Problem. Given bar heights of width 1 each, return the area of the largest rectangle that fits inside the histogram.

Constraints. 1 <= len(heights) <= 10^5, 0 <= heights[i] <= 10^4.

Examples. [2,1,5,6,2,3] gives 10 (heights 5 and 6, width 2) · [2,4] gives 4 · [5,4,3,2,1] gives 9

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Every maximal rectangle is limited by some bar’s height. For each bar, the widest rectangle at that height extends left and right until it meets something shorter.

An increasing stack finds both boundaries at the right moment: when a bar is popped because a shorter bar arrived, the right boundary is the current index, and the left boundary is just past whatever is now on top of the stack — which is the nearest shorter bar to its left.

Time $O(n)$. Space $O(n)$.

Three details:

• The sentinel 0. Iterating heights + [0] guarantees every remaining bar is popped and priced. Without it, an increasing histogram like [2,4] leaves everything on the stack unpriced and returns 0.
• left = stack[-1] + 1 if stack else 0. An empty stack means nothing shorter exists to the left, so the rectangle reaches index 0.
• >= rather than >. With equal heights, popping the earlier one is safe: it will be re-priced through the later equal bar, which has the same height and a wider span. [2,2,2] giving 6 confirms it.

[5,4,3,2,1] giving 9 is a good trace — the answer is height 3 across width 3, found mid-sweep rather than at a boundary.

Follow-ups you should expect: “Maximal Rectangle in a binary matrix (LC 85)?” — build a histogram per row (heights of consecutive ones above) and run this on each row; $O(mn)$ overall. “Why >= and not >?” — the equal-heights argument. “Trapping Rain Water (LC 42)?” — related but the geometry differs: you accumulate water above each position rather than rectangles beneath. “Divide and conquer?” — recurse on the minimum bar; $O(n \log n)$ average but $O(n^2)$ worst case.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

7 problems

1 easy4 medium2 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

AllEasyMediumHard

Unsolved onlyExportImportReset

• ○496Next Greater Element IeasyThe exact decreasing-stack template (II adds a circular array twist)
• ○739Daily TemperaturesmediumNext-greater-element, answering with a distance instead of a valueNeetCode 150amazonmetabloomberg
• ○503Next Greater Element IImediumThe exact decreasing-stack template (II adds a circular array twist)
• ○853Car FleetmediumNeetCode 150
• ○907Sum of Subarray MinimumsmediumFor each element, use a monotonic stack to find how many subarrays it's the minimum of, then sum `value * count` over all elements
• ○42Trapping Rain WaterhardA decreasing stack of "walls", computing water trapped above each popped valleyNeetCode 150LeetCode Top Interview 150amazongooglemetabloomberg
• ○84Largest Rectangle in HistogramhardThe increasing-stack variant, pricing out each bar's maximal rectangle as it gets poppedNeetCode 150googleamazonbytedance

Dry run

LC 739 with temps = [73, 74, 75, 71, 69, 72, 76, 73]. The stack column shows indices; the values are in brackets.

i	temp	pops (resolved)	stack after	out so far
0	73	—	[0(73)]	[0,0,0,0,0,0,0,0]
1	74	0 → out[0]=1	[1(74)]	[1,0,…]
2	75	1 → out[1]=1	[2(75)]	[1,1,0,…]
3	71	—	[2(75), 3(71)]	unchanged
4	69	—	[2, 3, 4(69)]	unchanged
5	72	4 → out[4]=1, 3 → out[3]=2	[2(75), 5(72)]	[1,1,0,2,1,0,0,0]
6	76	5 → out[5]=1, 2 → out[2]=4	[6(76)]	[1,1,4,2,1,1,0,0]
7	73	—	[6(76), 7(73)]	unchanged

Two things to read off that table:

• Total pops: 6. Total pushes: 8. Fourteen stack operations for an eight-element array — not 64. That is the amortised argument, stated concretely, and it is the answer to “why is this O(n) when there is a while inside a for”.
• Indices 6 and 7 are still on the stack at the end. They never saw a warmer day, so their answers stay 0. Leftovers on the stack are not a bug; they are the “no answer exists” case, and pre-filling out with zeros is what handles them.

Note step 5 popping two entries in one iteration while step 3 pops none. The work per iteration is wildly uneven; only the total is bounded.

The variant map

One template, four mutations. The direction of the comparison and what you store are the only things that change.

Variant	Stack ordering	Pop condition	Canonical problem
Next greater	decreasing	stack top < current	739 Daily Temperatures · 496 Next Greater Element I
Next smaller	increasing	stack top > current	1475 Final Prices With Special Discount
Previous greater / smaller	same, but scan right-to-left	mirror image	901 Online Stock Span
Span bounded on both sides	increasing, store indices	pop while top >= current, and compute width on pop	84 Largest Rectangle · 42 Trapping Rain Water · 85 Maximal Rectangle

Circular arrays: run the loop twice, do not duplicate the array

For “next greater in a circular array” (LC 503), iterate i over range(2 * n) and index with i % n, pushing only while i < n. Physically concatenating the array also works and costs $O(n)$ extra memory for no benefit — mentioning the modulo version is a small, cheap signal of fluency.

Largest Rectangle needs a sentinel, and it is the whole trick

In LC 84 a bar still on the stack at the end has no right boundary, so its rectangle is never computed. The fix is to append a sentinel height of 0, which is smaller than everything and therefore forces every remaining bar to pop and be measured. Without it the answer is silently too small on any non-decreasing input.

Pitfalls

• Storing values instead of indices. out[j] = i - j needs j. Once you have pushed only the value, the position is gone and distance questions become unanswerable. Push indices; read values through them.
• Using < where <= belongs, or the reverse. With equal values, <= pops the earlier equal element and < keeps it. For “days until strictly warmer” that choice changes the answer on flat runs like [73, 73, 74].
• Forgetting the leftovers. Anything still on the stack has no answer. Pre-fill the output with the default (0, or −1) rather than trying to handle it afterwards.
• Omitting the sentinel in span problems. LC 84 and LC 85 both need it. This produces a plausible answer that is wrong only on some inputs, which is the hardest kind of bug to spot in an interview.
• Claiming $O(n)$ without being able to justify it. The nested while looks quadratic. Be ready to say: each index is pushed exactly once and popped at most once, so total stack operations are bounded by $2n$ regardless of how uneven individual iterations are.

Interview follow-ups

They ask	What they’re checking	The answer
“There’s a while inside a for — why is it $O(n)$?”	Amortised reasoning	Each index is pushed once and popped at most once, so total stack operations are at most $2n$. Individual iterations vary wildly; only the total is bounded
“What is on the stack, in words?”	Whether you understand the invariant	Every index whose answer is not yet known, kept in decreasing value order — so a new element resolves a prefix of them and never has to look deeper
“Make it work on a circular array”	Adaptability	Loop i over 2n and index i % n, pushing only while i < n
“Now I want the largest rectangle in the histogram”	Whether you see the same pattern	Increasing stack, compute width on each pop, and append a sentinel 0 so every bar is forced out and measured
“Can you do it in $O(1)$ space?”	Whether you know the limits	Not in general — the stack can hold $n$ entries (a strictly decreasing input). For the count of pops only, sometimes; for per-element answers, no
“Same problem, but as a stream”	Practical modelling	Works unchanged for “previous greater” (LC 901 Stock Span). “Next greater” cannot be answered in a stream at all, because the answer depends on the future

Self-check

pch.quizTag Monotonic stack — self-check

1. What do the entries on a monotonic stack represent?

   A The largest values seen so far, in order B Indices whose answer is still unknown, kept in decreasing value order C A sliding window of the last k elements D The answer being built up in reverse
   pch.quizShowAnswer

   B — Indices whose answer is still unknown, kept in decreasing value order — This is the invariant the whole pattern rests on. Because entries are ordered by value, a new element resolves a prefix of them and never needs to look deeper — which is what makes the pop loop cheap in aggregate.

2. The pop loop is nested inside the scan loop. Why is the algorithm still O(n)?

   A The inner loop runs at most a constant number of times per iteration B Each index is pushed once and popped at most once, so total stack operations are bounded by 2n C The stack never exceeds a constant size D Python optimises while loops over lists
   pch.quizShowAnswer

   B — Each index is pushed once and popped at most once, so total stack operations are bounded by 2n — An amortised argument, not a per-iteration one. One iteration may pop five entries and the next may pop none; the bound is on the sum across the whole run.

3. Why push indices rather than values?

   A Indices are smaller integers, so it saves memory B Because distance answers like out[j] = i - j need j, and a value cannot recover its position C Values would break the monotonic ordering D It makes no difference
   pch.quizShowAnswer

   B — Because distance answers like out[j] = i - j need j, and a value cannot recover its position — Push indices and read values through them. The moment a problem asks 'how far' rather than 'what value', storing values makes the question unanswerable.

4. In Largest Rectangle in a Histogram, why append a sentinel height of 0?

   A To avoid an empty-stack check B To force every bar still on the stack to pop and have its rectangle measured, since it has no right boundary otherwise C To make the stack strictly increasing D It is an optimisation and can be omitted
   pch.quizShowAnswer

   B — To force every bar still on the stack to pop and have its rectangle measured, since it has no right boundary otherwise — A bar left on the stack never got a right boundary, so its rectangle is never computed. The sentinel is smaller than every real height, so it forces all of them out. Omitting it gives an answer that is too small on non-decreasing inputs — a wrong answer that passes many tests.

5. The problem is 'next greater element in a circular array'. What is the clean approach?

   A Concatenate the array with itself and run the usual algorithm B Iterate i over 2n and index with i % n, pushing only while i < n C Run the algorithm twice and merge the results D Reverse the array first
   pch.quizShowAnswer

   B — Iterate i over 2n and index with i % n, pushing only while i < n — Both work, but the modulo version uses no extra memory. Concatenating costs O(n) space for no benefit, and mentioning the difference is a cheap signal of fluency.

Recall card

• Cue — “next/previous greater or smaller”, or a span bounded by smaller values on both sides.
• Invariant — the stack holds indices whose answer is unknown, in decreasing (or increasing) value order.
• Template — for each i: while stack and cmp(a[stack[-1]], a[i]): j = pop; out[j] = f(i, j), then push(i).
• Complexity — $O(n)$ amortised ($\le 2n$ stack operations), $O(n)$ space worst case.
• Remember — push indices; pre-fill the output for the leftovers; span problems need a sentinel.
• Fails when — the query is about a window (use a monotonic deque) or a k-th value (use a heap).

Recap

• A monotonic stack holds indices in increasing or decreasing order of their values, popping whenever a new element breaks that order.
• Decreasing stack -> “next greater element” style questions. Increasing stack -> histogram/area style questions where a short bar caps taller ones.
• Every index is pushed once and popped at most once, so the total work is $O(n)$ even with a while loop nested inside the main for loop.
• The same scaffolding solves next-greater/smaller, daily temperatures, histogram area, rainwater trapping, and subarray-minimum-sum questions — only what you compute on a pop changes.

Next: Prefix Sums and Difference Arrays — answering range-sum queries in $O(1)$ after a single $O(n)$ preprocessing pass.