Stack + Monotonic

Reader guide and study workflow · Complete course map

For temperatures [71,69,69,73], find how long each day waits for a strictly warmer day. A direct model scans the future separately from every day; the answer is [3,2,1,0].

Store questions that have no answer yet

The repeated work is rereading future days. Reverse the responsibility: when a new day arrives, ask which earlier unresolved days it answers. After the first three values, indices 0,1,2 are all unresolved. The two 69s must remain distinct because their distances to the future answer differ.

A new temperature 73 resolves index 2, then 1, then 0. Why is checking the most recent unresolved index enough? Unresolved temperatures are non-increasing from oldest to newest. If the new day is not warmer than the newest, it cannot answer any older, at-least-as-warm day. If it is warmer, remove that newest question and continue. Store indices so each resolved wait is today-index.

A removed index is final: if an earlier warmer day existed, it would already have resolved it. Each index is inserted once and removed at most once, so a loop that removes several entries at one arrival still performs linear total work. Equal arrivals do not resolve a strictly-warmer question.

This derives a stack from the order in which questions become answerable. Brackets, expression evaluation, and histogram widths also use stacks, but their entries represent different unfinished work. In the workshop, name each entry and the event that permits removing it before copying any loop.

Prerequisites and readiness

Know last-in-first-out order, slice indexing, signed integer division, and amortized analysis. Be able to say what one stack entry represents and exactly what event makes it final.

Reasoning workshop: what unfinished work is on the stack?

Nesting, values, and candidates are different states

Bracket validation stores unmatched opening types. RPN evaluation stores completed subexpression values. A calculator saves suspended outer result/sign pairs. A monotonic stack stores candidate indices waiting for a future boundary. Their shared LIFO storage does not make their invariants interchangeable.

([)] contains balanced counts but fails nesting when ) meets [ at the top. RPN 7 -3 / returns -2: pop the right operand before the left and truncate toward zero. For 1-(2-(3+4)), the inner sum is 7, the middle expression is -5, and the outer result is 6. A saved minus applies to the whole parenthesized value, not just its first number. Commit the final pending number even when the expression does not end with a closing parenthesis.

Equal values reveal the monotonic convention

For temperatures [70,70,71], keep both 70 indices because an equal temperature is not warmer. The final 71 pops index 1 with wait 1 and index 0 with wait 2. Each popped answer is final: no warmer day appeared earlier, or that index would already have left the stack.

For histogram [2,2,2], equal heights may remain on the increasing stack. The virtual zero sentinel eventually pops them, and the earliest representative sees the full width 3, producing area 6. On [2,1,2], the middle height 1 spans all three bars, while the height-2 bars each have width 1; the maximum is 3. The rectangle width excludes both boundary bars, hence right-left-1.

Count work by the lifetime of an entry

An index enters the monotonic stack once and leaves at most once. A nested while loop may perform many pops on one arrival, but the total pops across the whole scan cannot exceed the pushes. This gives O(n) aggregate stack operations. Go slice append can occasionally allocate and copy; that is also amortized rather than a strict per-call constant-time promise.

Min Stack attaches the minimum of the entire prefix to every depth. Push 2, then 1, then 1; after one pop the minimum is still 1. Keeping only one uncounted copy of the minimum would fail this trace. Constructor calls must create independent state, and Top/GetMin are valid only when nonempty.

Lexical paths are not filesystem resolution

In /a/.../../b//./, the component ... is an ordinary name and the following .. removes it, leaving /a/b. Only whole components . and .. are special. The routine performs no filesystem access and cannot resolve symlinks; using it alone to claim a path is confined to a safe directory would exceed the algorithm's contract.

Build independent oracles

Scan every later day for the first warmer temperature on small arrays. Enumerate all histogram intervals and compute width times the minimum height. Evaluate generated arithmetic expression trees directly, then serialize them to postfix or parenthesized infix form. These slower specifications do not repeat the optimized stack logic and therefore expose wrong comparison signs, widths, and operand order.

Pattern reference

Use these summaries after deriving the state and the reason each update is safe. The patterns name decisions already justified above.

Pattern A: Matching delimiters

Use when: you need to validate or parse nested brackets.

Invariant: stack holds unmatched opening brackets in order.

Skeleton:

stack = []
for ch in s:
    if open(ch): push ch
    else:
        if stack empty or not matches(top, ch): return false
        pop
return stack empty

Problems:

• valid-parentheses.

---

Pattern B: Token stack for paths

Use when: you need to normalize a path with ".." and ".".

Invariant: stack holds the canonical path components so far.

Skeleton:

stack = []
for token in split(path, '/'):
    if token == '' or token == '.': continue
    if token == '..': if stack not empty: pop
    else: push token
return '/' + join(stack)

Problems:

• simplify-path.

---

Pattern C: Min stack

Use when: you need O(1) min queries with a stack.

Invariant: each frame stores (value, minSoFar).

Skeleton:

push(x): stack.push([x, x if stack empty else min(x, stack.top.min)])
pop(): stack.pop()
getMin(): stack.top.min

Problems:

• min-stack.

---

Pattern D: Reverse Polish evaluation

Use when: expression is given in postfix form.

Invariant: stack holds values of the current expression prefix.

Skeleton:

for token in tokens:
    if number: push
    else:
        b = pop; a = pop
        push(apply(a, b, token))
return pop

Problems:

• evaluate-reverse-polish-notation.

---

Pattern E: Monotonic decreasing stack (next greater)

Use when: you need the next greater element to the right.

Invariant: the stack stores unresolved indices with non-increasing values; equal temperatures remain unresolved.

Skeleton:

stack = []  // indices
for i in 0..n-1:
    while stack not empty and nums[i] > nums[stack.top]:
        idx = pop
        answer[idx] = i - idx
    push i

Problems:

• daily-temperatures.

---

Pattern F: Monotonic increasing stack (largest rectangle)

Use when: you need the max area rectangle in a histogram.

Invariant: the stack stores indices with non-decreasing heights; a strictly lower arriving height triggers pops.

Skeleton:

stack = []
for i in 0..n:  // include sentinel at n with height 0
    h = (i == n) ? 0 : heights[i]
    while stack not empty and h < heights[stack.top]:
        height = heights[pop]
        width = (stack empty) ? i : i - stack.top - 1
        best = max(best, height * width)
    push i

Problems:

• largest-rectangle-in-histogram.

---

Pattern G: Calculator with sign stack

Use when: you have +, -, and parentheses only.

Invariant: result is the sum of committed operands in this scope, num is the pending number, and sign applies to that pending operand. The stack saves outer result/sign pairs.

Skeleton:

stack = []
sign = 1
result = 0
num = 0
for ch in s:
    if digit: num = num*10 + digit
    if ch in '+-': result += sign * num; num = 0; sign = (ch == '+') ? 1 : -1
    if ch == '(':
        push(result); push(sign)
        result = 0; sign = 1
    if ch == ')':
        result += sign * num; num = 0
        outerSign = pop(); outerResult = pop()
        result = outerResult + outerSign * result
result += sign * num  // commit a final number outside parentheses
return result

Problems:

• basic-calculator.

---

When to use Stacks (checklist)

• Nested structures or matching pairs appear.
• You need the next greater/smaller element efficiently.
• You must evaluate or parse expressions in one pass.

Common failures (checklist)

• Forgetting to flush the stack with a sentinel value.
• Mixing indices and values inconsistently in the stack.
• Mishandling unary minus in calculators.
• Not resetting numbers when encountering operators.

Problem mapping

• valid-parentheses: matching stack.
• simplify-path: component stack.
• min-stack: track min per frame.
• evaluate-reverse-polish-notation: evaluation stack.
• daily-temperatures: monotonic decreasing stack.
• largest-rectangle-in-histogram: monotonic increasing stack.
• basic-calculator: sign stack with parentheses.

Reconstruction lab and answer key

Close the worked examples before attempting these new cases. Rebuild the state and justify the update, then compare with the model answer.

Valid Parentheses

For prefix "{[()]", write the entire unresolved stack and say what next character can empty it.

Model answer

Only { remains. The () pair and then [] pair have closed in nesting order. A } empties the stack; matching any other closing type must fail.

Simplify Path

Reconstruct the component stack for "/../../.cache/./x/..". Which tokens must be treated as literal names?

Model answer

The two initial .. components leave the stack empty at root. .cache is a literal name and is pushed; . does nothing; x is pushed and then popped by ... The result is "/.cache"; only a whole token equal to . or .. is special.

Min Stack

After pushing 4, then -2, then 7, then -2, write the minimum stored at every depth. What remains after two pops?

Model answer

The prefix minima are [4,-2,-2,-2]. Two pops remove the last -2 and 7, leaving values [4,-2] and minima [4,-2]. GetMin remains -2, and Top is -2.

Evaluate Reverse Polish Notation

Reconstruct the stack after each operator in ["12","3","-","2","*","5","/"]. Which pop is the right operand?

Model answer

After subtraction the stack is [9]; after multiplication [18]; after division [3]. At each operator the first value popped is the right operand, so the last operation is 18/5, truncated toward zero.

Daily Temperatures

For [65,64,66], which unresolved indices does the last day remove, and why can each answer be finalized immediately?

Model answer

It pops index 1 with wait 1, then index 0 with wait 2. Neither saw an earlier strictly warmer day; otherwise it would already have been popped. The last day is therefore the first warmer one, not just some warmer one.

Largest Rectangle in Histogram

At incoming index 3 of [1,4,4,0], derive both rectangles popped at height 4, including their left boundaries.

Model answer

Pop index 2 first: left boundary is index 1, width=3-1-1=1, area 4. Pop index 1 next: left boundary is index 0, width=3-0-1=2, area 8. The equal left bar first limits one representative; its later pop exposes the full plateau.

Basic Calculator

In "10-(4+2)", what outer frame is saved at (, what inner result is restored at ), and why must num be zero before the final commit?

Model answer

Save (outerResult=10, outerSign=-1). The inner result is 6, restoring 10-6=4. Committing the pending 2 at ) must also reset num; otherwise end-of-input adds it again. A saved frame carries both accumulated value and pending outer sign.

Problems in this module

• Valid Parentheses
• Simplify Path
• Min Stack
• Evaluate Reverse Polish Notation
• Daily Temperatures
• Largest Rectangle in Histogram
• Basic Calculator

Interactive checkpoint

Open the Stack + Monotonic quiz. The questions use exact, objectively gradeable answers. Work the reasoning drills above before opening their model answers.

Earlier-edition deep links

These anchors preserve links to headings from the original files. They do not reinstate superseded explanations.

Learner experience: how to make this topic stick

The moves to recognize

How to practice without turning it into grind

Debugging instincts to build

A small way to make it memorable