L17 · Monotonic Stack

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

Why this session exists

Next greater element, next smaller element, previous greater, previous smaller: monotonic stack, always. 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, it is easy, and it times out. 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 in an interview.

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

Equivalently, previous-greater can be done left to right by reading stack[-1] before pushing i — the top at that moment is the nearest earlier element greater than v. That formulation is often cleaner because it lets one pass answer both directions.

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: if you need the k-th greater element rather than the nearest, or the greatest element in a window rather than the next one, the stack is the wrong shape. The former wants a different structure entirely; the latter is a monotonic deque, which is next session.

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. The inner while can run n times in one iteration, but only if it did nothing in the previous n iterations.

Solo timed

15 minutes each, timer visible.

• Next Greater Element I — 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 — for each bar, the rectangle it anchors extends left to the previous smaller bar and right to the next smaller bar; width is right - left - 1. Append a sentinel bar of height 0 so the stack fully drains at the end.
• 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.

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 on the first strictly decreasing prefix. 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 loop again after the main pass or push a sentinel of height 0 to force the drain.

Off-by-one in the width. After popping the bar at index p, the width is i - stack[-1] - 1 using the new top after the pop, 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. Any code path that reconsiders a popped index has broken the amortised bound and probably the correctness too.

Complexity

Time: O(n) amortised. The outer loop runs n times. The inner while has no per-iteration bound, 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 operations ≤ 2n.

This is a genuine amortised bound, not an average-case one — it holds for every input, including adversarial ones. Worth stating precisely, because "average case O(n)" would be a weaker and incorrect claim.

Space: O(n). Worst case the stack holds every index simultaneously, which happens exactly when the input is monotonically decreasing (for a next-greater search) and nothing is ever popped. The output array is a separate O(n).

For the histogram variant the bounds are identical; appending one sentinel bar changes n to n + 1 and nothing else.

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.