Monotonic Stack

Review boundary and corrected contracts

With strict next-greater comparison, equal values remain: the pending stack is non-increasing, not strictly decreasing. Each pop fixes the first greater index, because every intervening value has already failed that comparison. The output sentinel −1 is an index convention.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Recognise next-greater and next-smaller questions instantly and answer them in one linear pass by maintaining a stack whose contents are always sorted.

Series: LeetCode — From Basics to Production-Ready · Session 17 / 65 · Phase 1 · Core patterns

Prerequisites. Plain stacks (push/pop/peek and the empty-stack guard) and comfort reading an amortised complexity argument. Nothing else — this session derives the pattern from scratch.

Watch first

Optional companions from the original list: Next Greater Element I, Largest Rectangle, and Histogram whiteboard derivation. Compare their equal-height and sentinel rules with the code below. External video availability is not verified here; the lesson is self-contained.

Why this session exists

For all-position nearest-greater/smaller queries on a static array, a monotonic stack is a strong default. Recognise it instantly and a set of problems that look unrelated — Daily Temperatures, Largest Rectangle in Histogram, Trapping Rain Water, stock spans — become the same eight lines with different bookkeeping.

The reason this is such high leverage is the gap between the obvious solution and the good one. The obvious solution to "for each element, find the next larger element to its right" is a nested loop: O(n²). It is correct, but its quadratic worst case is unsuitable for large inputs. The monotonic stack gets it to O(n) with no extra cleverness beyond one rule about what the stack is allowed to contain, and the amortised argument for why it is linear is short enough to say out loud under a tight review.

There is a deeper reason to care. The monotonic stack is the first pattern in this series where the data structure holds pending obligations rather than data. Each element sitting in the stack is a question that has not yet been answered: "what is the next thing bigger than me?" The current element answers, and thereby discharges, every pending question it is big enough to satisfy. Once you see it that way, Largest Rectangle in Histogram stops being a trick and becomes a consequence.

Blank-file warm-up

Five minutes, empty file, no notes. Write the core loop:

while stack and a[stack[-1]] < a[i]:
    ...

Then answer, in writing, three questions: what does the stack hold — values or indices? What do you do inside the while body? What is left in the stack when the outer loop ends, and what does that leftover mean?

If you wrote values rather than indices, that is today's finding. Almost every real monotonic-stack problem needs distances or widths, and you cannot recover a position from a value.

Pattern anatomy

The shape that summons this pattern: for every element, find the nearest element in some direction that stands in a given order relation to it.

The invariant is one sentence:

Reading bottom to top, the values indexed by the stack are always in non-increasing order (for a next-greater search).

Maintaining that invariant is the entire algorithm. When a new element arrives that would break the order, you do not discard it and you do not sort — you pop every element it violates, and each pop is the moment that element's question gets answered.

def next_greater(nums):
    """res[i] = index of the next element strictly greater than nums[i], else -1."""
    n = len(nums)
    res = [-1] * n
    stack = []                          # indices; values non-increasing bottom -> top
    for i, v in enumerate(nums):
        while stack and nums[stack[-1]] < v:
            res[stack.pop()] = i        # v is the answer for that pending index
        stack.append(i)
    return res                          # anything still in stack keeps its -1

Eight lines. Read the loop as a story: element i walks in; everyone in the stack who has been waiting for something bigger and finds v bigger, gets their answer and leaves; i then joins the queue of the still-unanswered.

The four variants differ by exactly two knobs — direction of travel, and the comparison operator:

• Next greater — left to right, pop while stack top < v
• Next smaller — left to right, pop while stack top > v
• Previous greater — right to left, pop while stack top < v
• Previous smaller — right to left, pop while stack top > v

A different left-to-right formulation answers previous strictly greater for the current element: first pop all indices whose values are <= v, then read the top, then push i. Merely reading the top of the next-greater template is wrong on duplicates. On [2, 2, 3], the previous-strictly-greater answers are [-1, -1, -1], not [-1, 0, ...].

def previous_greater(nums):
    result = [-1] * len(nums)
    stack = []
    for i, value in enumerate(nums):
        while stack and nums[stack[-1]] <= value:
            stack.pop()
        result[i] = stack[-1] if stack else -1
        stack.append(i)
    return result

Popped earlier values can never be a better previous-greater candidate for a later position: the current value is at least as large and closer. This is a candidate-discarding proof, distinct from the next-greater template where popping records the popped index's answer. To combine directions, specify each direction's strictness rather than mixing these pop rules.

Strict versus non-strict matters when duplicates exist. < versus <= decides whether an equal element counts as "greater". For Daily Temperatures the problem says warmer, so strictly greater, so <. For histogram problems the choice affects whether equal bars are treated as one block, and either convention gives the right final answer provided you are consistent — but only if you are consistent.

The cue

How you recognise this from the problem statement:

1. The literal words "next greater", "next smaller", "previous greater", "warmer", "taller", "how many days until". Diagnostic. Stop and write the template.
2. "For each element, find the nearest ... to the left/right". The word nearest combined with a comparison is the fingerprint. Nearest without a comparison is usually a different pattern.
3. Span or width bounded by comparisons. Largest rectangle, maximal area, stock span, "how far can this element extend before hitting something bigger". The width is right_boundary - left_boundary - 1, and both boundaries are monotonic-stack outputs.
4. The obvious solution is a nested loop over pairs with an early break. That early-break structure — scan right until you find something bigger, then stop — is exactly what the stack collapses into linear time.
5. Constraints around n <= 10^5 where an O(n²) pair scan is roughly 10^10 operations. The problem is telling you a quadratic pair scan will not pass.

The anti-cue: the one-stack nearest-neighbour template does not directly answer the k-th greater element or window maxima. Some fixed-k problems use multiple stacks; general rank queries may need other structures. Window maxima need expiry from the front as well as dominance removal from the back, hence a monotonic deque.

Guided solve

Daily Temperatures. Given temperatures[i], return answer[i] = the number of days you must wait after day i for a warmer temperature, or 0 if it never gets warmer.

The brute force is immediate: for each i, scan forward until you find something larger. Worst case — a strictly decreasing array — every scan runs to the end and it is O(n²). Say that out loud, then say why you are not going to do it.

Now the reframing that produces the stack. Instead of asking "for each day, what comes next", ask "for each day, which earlier days does today answer?" Today answers every pending earlier day whose temperature is below today's. And here is the key structural fact: the set of pending days always has non-increasing temperatures, because if an earlier pending day had been colder than a later one, the later one would have already answered it and removed it. Pending days are therefore sorted by construction. So the days today can answer are exactly a contiguous run from the top of the stack, and you stop the moment you hit one you cannot answer.

That is the entire derivation. The stack is not a trick added to the problem; it is what the set of unanswered questions inevitably looks like.

Trace temperatures = [73, 74, 75, 71, 69, 72, 76, 73]:

• i=0 (73). Stack empty. Push. Stack: [0]
• i=1 (74). 73 < 74 → pop 0, res[0] = 1 - 0 = 1. Stack empty, push 1. Stack: [1]
• i=2 (75). 74 < 75 → pop 1, res[1] = 2 - 1 = 1. Push 2. Stack: [2]
• i=3 (71). 75 < 71 false. Push 3. Stack: [2, 3] — temps 75, 71, non-increasing, invariant holds
• i=4 (69). 71 < 69 false. Push 4. Stack: [2, 3, 4] — 75, 71, 69
• i=5 (72). 69 < 72 → pop 4, res[4] = 5 - 4 = 1. 71 < 72 → pop 3, res[3] = 5 - 3 = 2. 75 < 72 false, stop. Push 5. Stack: [2, 5]
• i=6 (76). 72 < 76 → pop 5, res[5] = 1. 75 < 76 → pop 2, res[2] = 6 - 2 = 4. Stack empty, push 6. Stack: [6]
• i=7 (73). 76 < 73 false. Push 7. Stack: [6, 7]

Loop ends. Indices 6 and 7 remain — no warmer day ever comes — so res[6] = res[7] = 0, which the initialisation already gave us.

Result: [1, 1, 4, 2, 1, 1, 0, 0].

Look at i=5. It popped two elements. Look at i=3 and i=4. They popped none. The per-element work is wildly uneven, and that is exactly why the complexity argument has to be amortised rather than per-iteration.

Why it is O(n). Every index is pushed exactly once, at its own iteration. Every index is popped at most once, because once popped it is gone forever. Therefore total pushes ≤ n and total pops ≤ n, so total work across the entire run is at most 2n regardless of how lumpy any individual iteration looks. An iteration can pop k pending indices only after at least k pushes have created them. Earlier iterations may also have popped other indices; the proof uses total pushes and pops, not a requirement that preceding iterations did no work.

A trap worth naming: storing values in the stack instead of indices. Daily Temperatures needs i - popped_index, and Largest Rectangle needs widths. A value tells you what, never where. Store indices and read nums[stack[-1]] when you need the value — it costs one extra character and saves you from rewriting the solution when the follow-up asks for distance instead of existence.

Solo timed

15 minutes each, timer visible.

• Next Greater Element I — under its distinct-values contract, run the template on nums2 to build a value-to-next-greater dictionary, then look up each element of nums1. The mapping step is the whole problem; the stack part is the template unchanged.
• Largest Rectangle in Histogram — use smaller/equal boundaries consistently, as in the worked answer below. A virtual height-0 sentinel processes every remaining positive-height rectangle; zero-height bars may remain because their area is zero.
• Trapping Rain Water — the stack variant pops a valley bar and computes the water bounded by the new stack top on the left and the current bar on the right; the bounded height is min(left, right) - valley. Two pointers also solves this in O(1) space; do the stack version first, then the two-pointer version and compare which you would rather write cold.

Worked answer — histogram boundaries and equal heights

For nonnegative bar heights, keep indices with non-decreasing heights. When a smaller height arrives, pop p: the current i is the first strictly smaller height on its right. After the pop, the new top is a previous smaller or equal height under this strict-pop convention, or −1 if none. Everything between that boundary and i is at least heights[p], so the candidate area is heights[p] * (i - left - 1).

def largest_rectangle(heights):
    stack = []
    best = 0
    for i in range(len(heights) + 1):
        current = heights[i] if i < len(heights) else 0
        while stack and heights[stack[-1]] > current:
            p = stack.pop()
            left = stack[-1] if stack else -1
            best = max(best, heights[p] * (i - left - 1))
        if i < len(heights):
            stack.append(i)
    return best

On [2, 2], the sentinel first pops index 1 with width 1, then index 0 with width 2, producing area 4. The newer equal bar need not receive its widest possible rectangle: the older equal bar represents the wider span later. On [0, 2, 0], zeros remain but area 2 is still measured. On [2, 1, 2], the height-1 bar ultimately spans all three positions, area 3; i - p would miss its extension to the left.

Every positive-height maximal rectangle has a minimum-height bar; with ties, the leftmost surviving equal minimum eventually represents that full span when a smaller right boundary or the sentinel arrives. This establishes that taking the maximum of these candidates misses no positive optimum. Each index still pushes once and pops at most once.

Common failure modes

Storing values instead of indices. Works for existence questions, fails the moment a distance or width is required. Default to indices always.

Wrong comparison strictness with duplicates. < versus <= changes which of several equal elements answers which. Decide from the problem wording — "warmer" means strictly — and apply it consistently in both the pop condition and any boundary computation.

Forgetting the stack is non-empty in the while guard. while nums[stack[-1]] < v without the stack and prefix raises IndexError immediately when the initially empty stack is inspected, or after the final pop. It is the same guard as plain stacks and it is forgotten just as often.

Not draining the stack at the end. In next-greater the leftovers correctly keep their sentinel default, but in histogram problems the leftovers represent real rectangles that must still be measured. Either explicitly process the remaining rectangles or use a virtual height-0 sentinel for nonnegative heights. With a strict > pop, zeros need not drain: they contribute no positive area.

Off-by-one in the width. After popping the bar at index p, set left = stack[-1] if stack else -1; the width is i - left - 1, using the new top or the left-edge sentinel, not i - p. This is the single most common bug in Largest Rectangle, and it produces answers that are close enough to look plausible.

Recomputing the answer for popped elements. Once an index is popped its answer is final. Repeatedly rescanning popped indices can destroy this linear bound. A separately bounded second pass is not automatically wrong, but needs its own accounting.

Myth: The inner while loop can iterate O(n) times in a single outer iteration, so the algorithm must be O(n²) in the worst case.

Why: Per-iteration cost is the wrong unit of accounting here. Each index enters the stack exactly once and leaves at most once, so total pops across the whole run are bounded by n no matter how they are distributed. Every pop is charged to the unique earlier push of that index; earlier iterations may themselves have performed other pops. Total work is bounded by 2n, which is O(n). This amortised argument is the point of the pattern, and saying it explicitly is what separates a candidate who memorised the template from one who understands it.

Steps 1: Because an element's next-greater question is answered by the first larger element to its right, an element remains 'pending' only while everything seen since has been no larger.

Steps 2: Because any pending element that was smaller than a later element would already have been answered and removed by it, the set of pending elements is necessarily non-increasing in value.

Steps 3: Because that set is sorted by construction, the elements a new value can answer form a contiguous run from the top, and the first element it cannot answer terminates the scan — no deeper inspection is ever needed.

Steps 4: Because each index is pushed exactly once and popped at most once, total stack operations are bounded by 2n, so the algorithm is O(n) amortised despite unbounded per-iteration cost.

Steps 5: Indices make distances and widths computable, but histogram area still needs a boundary convention, an empty-stack case and a final positive-height drain; these are derived below.

Steps 6: Testable prediction: run the template on a strictly decreasing array such as [5,4,3,2,1]. Zero pops occur, the stack ends holding all n indices, and every answer is the sentinel -1. If your implementation pops anything on that input, your comparison is reversed.

Picture: A queue of people waiting to be served, each holding a number, and the queue is always in descending order because anyone holding a smaller number than a newcomer gets served immediately and leaves. When someone with a big number walks in, everyone below them is served in one sweep and the queue shortens.

Trigger: Fires on 'next greater', 'next smaller', 'nearest larger to the right', 'how many days until warmer', and on any span or width bounded by a comparison.

Name: Monotonic stack

Gain: O(n) time, O(n) space, one pass, and the same pass yields both the answer and the distance. Generalises directly to histogram and rain-water problems.

Cost: The amortised argument is unintuitive under pressure; index-versus-value and strict-versus-non-strict choices are easy to get wrong and produce plausible-looking answers.

Name: Nested loop with early break

Gain: A simple independent oracle; linear work on strictly increasing input where each nonfinal index finds its answer immediately.

Cost: O(n²) worst case on a non-increasing array: n(n−1)/2 pair comparisons, about five billion at n = 100,000, before loop overhead.

Name: Segment tree versus sparse table over range maxima

Gain: A standard max segment tree supports O(log n) range queries and point updates after O(n) construction. A max sparse table instead supports O(1) static range queries after O(n log n) preprocessing; it is not an O(log n) point-update structure.

Cost: Extra machinery compared with one O(n) nearest-neighbour pass. Neither a plain maximum aggregate nor its complexity claim automatically supplies k-th-greater rank queries; those need additional state or a different algorithm.

Pick: Use the monotonic stack whenever the question is about the NEAREST element in one direction under a comparison. Consider a segment tree for changing data or more general range queries; static all-position nearest-element queries do not need one.

Memory hook — the four-way dial

All four questions in this family are one template with two switches. Burn in the dial, not four separate solutions:

• Direction switch — next means iterate left to right; previous means iterate right to left. That is the loop, nothing else.
• Comparison switch — greater means pop while the stack top is smaller; smaller means pop while the stack top is larger.

The mnemonic: "pop the losers." Whatever quality you are searching for, the current element pops everything on the stack that loses to it under that comparison, and the current element is the answer for every one it pops. Say "pop the losers, push myself" as you type the loop and the operator falls out automatically.

The shape-of-the-code peg: the template is always guard, while, pop-and-record, push. Four beats. If your fingers produce four beats you have the template; if you find yourself writing a nested for, you have reverted to brute force.

What reviewers actually ask

These exercises test the gap between the obvious pair scan and the linear pending-index invariant; the suggested timer is practice guidance, not an interview-frequency or performance measurement.

• 739 · Daily Temperatures (Medium) — Practice selection. Probing whether you spot the pattern at all from the word "warmer". Follow-up: state the amortised bound and defend it against "but the while loop is linear".
• 496 · Next Greater Element I (Easy) — Practice selection. Probing the template plus the value-to-answer dictionary indirection. Follow-up: 503 · Next Greater Element II with a circular array.
• 84 · Largest Rectangle in Histogram (Hard) — Practice selection. Probing whether you can turn next-smaller-on-both-sides into a width. Follow-up: 85 · Maximal Rectangle, which is 84 run once per row over a prefix-height array.
• 42 · Trapping Rain Water (Hard) — Practice selection. Probing flexibility: the stack solution and the two-pointer solution both work. Follow-up: "do it in O(1) extra space" — that is the two-pointer version, so know both.
• 853 · Car Fleet (Medium) — Practice selection. Probing whether you can see a stack under a physics-flavoured story. Follow-up: return the fleet sizes, not just the count.
• 901 · Online Stock Span (Medium) — Practice selection. Probing the streaming variant, where the stack persists across calls instead of living inside one function.

What they are really testing across all six is the amortisation argument. Candidates who produce the template but cannot explain why it is linear are read as having memorised it.

Complexity

Time: O(n) amortised. The outer loop runs n times. The inner while can take O(n) in a single iteration, but every execution of its body performs one pop, and an index can be popped at most once in the entire run because it is never re-pushed. Total pops ≤ n, total pushes = n, so total stack pushes and pops ≤ 2n; comparisons and output writes add only O(n) further work.

This is a genuine amortised bound, not an average-case one — it holds for every input, including adversarial ones. Worth stating precisely: saying only "average case O(n)" would undersell the guarantee and could misleadingly suggest a dependence on an input distribution.

Space: O(n). Worst case the stack holds every index simultaneously, which happens on any non-increasing input, including all-equal values, because nothing is popped in a strictly-greater search. The output array is a separate O(n).

For the histogram variant the bounds are identical; the code below uses a virtual sentinel so it does not mutate the caller's list.

You can now…

• Recognise next-greater, next-smaller, previous-greater and previous-smaller as one template with two switches.

• Write the four-beat skeleton — guard, while, pop-and-record, push — cold, without notes.

• Defend the O(n) bound with the amortised push-once/pop-once argument instead of hand-waving.

• Explain why the stack contents are sorted by construction rather than by any explicit sorting step.

• Compute widths correctly after the pop, and say why using the popped index directly is wrong.

• Use a height-0 sentinel to process all positive-height rectangles; zero-height leftovers need not pop.

• Distinguish the one-stack nearest-neighbour template from fixed-k multi-stack variants, window deques, and dynamic range-query structures.

Quiz

Self-check (answer follows each question).

Q: Why is the monotonic stack O(n) even though the inner while loop has no per-iteration bound?

A: Each index is pushed exactly once and popped at most once across the entire run, so total pops are bounded by n regardless of distribution. An iteration that pops many elements is paid for by earlier iterations that popped none. Total work is at most 2n.

Q: Should the stack hold values or indices, and why?

A: Indices. Most problems in this family need distance or width — Daily Temperatures needs i minus the popped index, Largest Rectangle needs widths — and a value cannot be converted back into a position. Read nums[stack[-1]] when you need the value.

Q: For next-greater, is the stack increasing or decreasing from bottom to top?

A: Non-increasing bottom to top. Any element smaller than a later arrival would have been popped by it, so what remains can only be flat or descending.

Q: In Largest Rectangle in Histogram, after popping the bar at index p, what is the correct width and why is i - p wrong?

A: Set left = stack[-1] if stack else -1, then width is i - left - 1. The popped height extends left across already-popped taller bars to just after that boundary. With equal heights, the convention below leaves the older equal bar to represent a wider rectangle later; using p as the left edge misses valid width.

Q: You run the template on a strictly decreasing array [5,4,3,2,1]. What happens?

A: No pops occur at all, since each new value is smaller than the stack top. The stack ends holding all five indices and every answer stays at the sentinel -1. This is the O(n) space worst case.

Q: Next Greater Element II asks for the next greater in a CIRCULAR array. What single change to the template handles the wraparound?

A: Iterate over 2n positions using i % n for indexing, and only push indices during the first pass (i < n) so nothing is enqueued twice. The second pass answers any indices still pending after the wrap, and everything still in the stack after 2n iterations genuinely has no greater element anywhere.

Stretch: true

Spaced queue

Re-solve whatever is due before starting anything new today. Status ladder:

• cold — solved unaided, first attempt clean → next review in 60 days
• warm — solved but slowly or with a stumble → 21 days
• hint — needed a nudge to get started → 7 days
• failed — could not produce a working solution → 2 days, then 7 days

Daily Temperatures enters today. Largest Rectangle in Histogram enters separately and should be graded harder — it is the same pattern but the width arithmetic is a distinct skill, and getting the template right while getting i - stack[-1] - 1 wrong is still a wrong answer.

• Next greater, next smaller, previous greater, previous smaller — all four are the same eight lines with the direction and comparison operator changed.

• The stack holds pending questions, and the pending set is sorted by construction because anything out of order would already have been answered.

• Store indices, never values. Distances and widths are what most problems in this family actually want.

• O(n) is amortised: each index is pushed once and popped at most once, so total work is bounded by 2n for every input.

• In histogram width calculations, use i - left - 1 after the pop, where left is the new top or −1 if empty; not i - popped_index.

• A virtual height-0 sentinel processes the remaining positive-height rectangles without mutating the input; zeros may safely remain.

Corrective source notes

• Minimum Stack / Minimum Queue - Algorithms for Competitive Programming — A monotonic queue obtains linear total work by bounding each element’s insertions/removals. Checked 2026-10-07.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.