Stack + Monotonic

Stacks store unresolved items and let you process nested or "next greater" relationships in linear time. The key is a precise invariant: what each stack frame represents, and when it is pushed or popped.

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, 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: stack stores indices with decreasing values.

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: stack stores increasing heights; a pop finalizes rectangles.

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: sign carries the sign for the current scope.

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
        result = pop() * result + pop()

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.