When to Use a Stack?

Core Idea: LIFO (Last-In-First-Out). Process elements where the most recent item matters, or where a future element resolves something about a past element.

Pattern Recognition:

Key Insight:

Past Depends on Future: When you can't resolve an element until you see a future element, push it to stack. When you find the "answer" for stack elements, pop and process them.

Why Not Just Array? Stack enforces the "most recent first" discipline. When processing, you only care about the top - O(1) access to the relevant element.

Valid Parentheses

O(n) Time / O(n) Space

Goal: Check if brackets are properly matched and nested.

Technique: Matching Stack

Why Stack? Innermost bracket must close first. When we see ')', we need the most recent '(' - that's exactly what stack top gives us. LIFO matches nesting structure perfectly.

Key Insight: Push opening brackets. When closing bracket arrives, stack top must be matching opener. If not, or stack empty, invalid.

endPair := map[string]string{")":"(", "}":"{", "]":"["} var stack []string for _, c := range s: if match, ok := endPair[c]; ok: if len(stack)==0 || stack[top] != match: return false stack = stack[:len(stack)-1] // pop else: stack = append(stack, c) // push opener return len(stack) == 0

Don't Forget:

Check stack is empty at end - unmatched openers are invalid.

Min Stack

O(1) All Operations

Goal: Stack with O(1) push, pop, top, AND getMin.

Technique: Auxiliary Monotonic Stack

Why Two Stacks? Main stack for values. Monotonic decreasing stack for minimums. When we push a new minimum, it goes on both. When we pop, if it equals mono top, pop both.

Key Insight: Larger values pushed after a minimum will be popped before that minimum. So we don't need to track them in mono stack - they can never be the min while the smaller value exists.

type MinStack struct { stack []int monoStack []int // decreasing: tracks minimums } func (s *MinStack) Push(val int): if len(monoStack)==0 || monoStack[top] >= val: monoStack = append(monoStack, val) stack = append(stack, val) func (s *MinStack) Pop(): popped := stack[top]; stack = stack[:len-1] if popped == monoStack[top]: monoStack = monoStack[:len-1] func (s *MinStack) GetMin(): return monoStack[top]

Mono Stack Insight:

Only track values that could be min at some point.

Evaluate Reverse Polish Notation

O(n) Time / O(n) Space

Goal: Evaluate postfix expression like ["2","1","+","3","*"] = 9.

Technique: Operand Stack

Why Stack? In RPN, operators act on the two most recent operands. Stack naturally accumulates operands, and operator pops exactly what it needs. Result becomes new operand.

Key Insight: Numbers → push. Operator → pop two, compute, push result. Final answer is last item on stack.

var stack []int for _, token := range tokens: switch token: case "+", "-", "*", "/": b := stack[len-1]; stack = stack[:len-1] a := stack[len-1]; stack = stack[:len-1] switch token: case "+": stack = append(stack, a+b) case "-": stack = append(stack, a-b) case "*": stack = append(stack, a*b) case "/": stack = append(stack, a/b) default: val, _ := strconv.Atoi(token) stack = append(stack, val) return stack[0]

Order Matters:

For - and /, it's a op b where a is deeper in stack (second-to-top).

Daily Temperatures

O(n) Time / O(n) Space

Goal: For each day, find days until a warmer temperature.

Technique: Monotonic Decreasing Stack

Why Stack? Classic "next greater element" pattern. We can't answer "when is next warmer day?" until we see that warmer day. Push indices to stack; when warmer day arrives, it resolves all cooler days waiting on stack.

Key Insight: Stack holds indices of days "waiting for answer". When temp[i] > temp[stack.top], we found the answer for stack.top. Pop and record distance. Stack stays monotonic decreasing (in temperature).

res := make([]int, len(temps)) var stack []int // indices, mono decreasing by temp for i := 0; i < len(temps); i++: // Current temp resolves all smaller temps on stack for len(stack) > 0 && temps[stack[top]] < temps[i]: idx := stack[top] stack = stack[:len-1] res[idx] = i - idx // days until warmer stack = append(stack, i) return res // unresolved days stay 0

Next Greater Element:

Mono decreasing stack. Pop when you find something greater.

Car Fleet

O(n log n) Time / O(n) Space

Goal: Count how many car fleets arrive at destination.

Technique: Time-to-Target Comparison

Why Stack-like? Sort by position (closest to target first). For each car, calculate time to reach target. If a car behind takes LESS time, it would catch up and merge (same fleet). If MORE time, separate fleet.

Key Insight: Process from closest to target. Stack tracks fleet arrival times. If current car's time ≤ stack top, it merges (catches up). If time > stack top, it's a new fleet - push it.

// Sort by position descending (closest to target first) sort cars by position DESC var stack []float64 // arrival times of fleets for each car: time := (target - car.pos) / car.speed if len(stack)==0 || time > stack[top]: stack = append(stack, time) // new fleet // else: merges with fleet ahead (time <= stack top) return len(stack)

Key Formula:

time_to_target = (target - position) / speed. Compare times, not positions.

Largest Rectangle in Histogram

O(n) Time / O(n) Space

Goal: Find largest rectangle area in histogram bars.

Technique: Monotonic Increasing Stack

Why Stack? For each bar, we need its left and right boundaries (next smaller elements). When we see a shorter bar, it's the right boundary for all taller bars on stack. The bar below in stack is the left boundary.

Key Insight: Stack holds indices in increasing height order. When heights[i] < stack top, we found right boundary for top. Pop, calculate area using: height × (rightBound - leftBound - 1). Left bound is new stack top (or -1 if empty).

var stack []int // indices, mono increasing by height maxArea := 0 for i := 0; i <= len(heights); i++: // i==len or shorter bar: resolve taller bars for len(stack)>0 && (i==len || heights[stack[top]] >= heights[i]): h := heights[stack[top]] stack = stack[:len-1] width := i // right boundary if len(stack) > 0: width = i - stack[top] - 1 // between boundaries maxArea = max(maxArea, h * width) if i < len(heights): stack = append(stack, i) return maxArea

Next Smaller Element:

Mono increasing stack. Pop when you find something smaller.

Trapping Rain Water

O(n) Time / O(n) Space

Goal: Calculate total water trapped between bars after rain.

Technique: Monotonic Decreasing Stack

Why Stack? Water is trapped between two walls with a lower region between them. We can't know the right wall until we see it. Stack holds bars waiting for a taller bar to appear (their right boundary).

Key Insight: Unlike prefix-max approach (column by column), stack calculates water layer by layer horizontally. Each pop handles one horizontal layer of water between two walls.

The Three-Element Boundary Pattern:

When we pop from stack, we have access to three critical elements:

Why This Works: The monotonic decreasing property guarantees that after popping the bottom, the new top is taller (or equal). Combined with the current bar being taller than bottom, we have a valid "container" with walls on both sides.

var stack []int // indices, mono decreasing by height res := 0 for i := 0; i < len(height); i++: for len(stack)>0 && height[i] >= height[stack[top]]: bottomIdx := stack[top] // Element of interest stack = stack[:len-1] // Pop bottom if len(stack) > 0: // Need left wall leftIdx := stack[top] // Left boundary h := min(height[leftIdx], height[i]) - height[bottomIdx] w := i - leftIdx - 1 // Width between walls res += h * w stack = append(stack, i) return res

Column vs Layer Mental Model:

Array approach (prefix/suffix): For each column, calculate vertical water height = min(leftMax, rightMax) - height.

Stack approach: Fill water horizontally between two walls, layer by layer from bottom up. Same rightBound triggers multiple pops, each pop adds one layer on top of the previous.

Concrete Trace - [5, 2, 1, 3]:

Stack builds: [5, 2, 1] When i=3 (rightBound=3) arrives: Pop #1: bottom=1, left=2, right=3 h=min(2,3)-1=1, w=1 → Layer 1 (height 1→2) Pop #2: bottom=2, left=5, right=3 (SAME rightBound!) h=min(5,3)-2=1, w=2 → Layer 2 (height 2→3) Stop: 3 < 5 (rightBound < stack top)

Key: Within one rightBound's pop loop, successive pops add layers vertically. Each pop has a taller leftBound, filling a wider region. Stops when rightBound becomes the limiting wall.

Layer-by-Layer:

Each pop calculates one horizontal water layer. The same "pool" may generate multiple pops as we fill it layer by layer from bottom up.

Must Have Left Wall:

After popping bottom, if stack is empty there's no left wall - no water can be trapped. Always check stack not empty before calculating.

Stack Patterns Summary

1. Matching/Nesting:

Use When: Validating balanced structures (parentheses, tags, nested calls).

Template: Push openers, pop and match on closers.

Example: Valid Parentheses.

2. Expression Evaluation:

Use When: Evaluating RPN, calculators, parsing expressions.

Template: Push operands, pop for operators, push result.

Example: Evaluate RPN.

3. Next Greater Element (Mono Decreasing):

Use When: "Find next larger/warmer/higher element."

Template: Push to stack. When greater found, pop and resolve.

Example: Daily Temperatures.

4. Next Smaller Element (Mono Increasing):

Use When: "Find boundaries", "largest rectangle", "next smaller".

Template: Push to stack. When smaller found, pop and resolve.

Example: Largest Rectangle in Histogram.

5. Auxiliary Stack for O(1) Queries:

Use When: Need O(1) min/max while maintaining stack operations.

Template: Second stack tracks min/max at each state.

Example: Min Stack.

Common Thread:

Stack = "most recent matters" or "waiting for future to resolve past". Monotonic stacks efficiently find next greater/smaller by maintaining sorted order.

Monotonic Stack Cheat Sheet

When to Use:

Finding next greater or next smaller element for each position in O(n).

Mono Decreasing (Next Greater):

// Stack top is smallest. Pop when greater found. for i := range arr: for stack not empty && arr[stack.top] < arr[i]: // arr[i] is the "next greater" for stack.top pop and process push(i)

Mono Increasing (Next Smaller):

// Stack top is largest. Pop when smaller found. for i := range arr: for stack not empty && arr[stack.top] > arr[i]: // arr[i] is the "next smaller" for stack.top pop and process push(i)

Store Indices: Almost always store indices, not values. Need index to calculate distances and access original values.

Leftover Items: Elements remaining on stack have no next greater/smaller. Handle based on problem (often default to 0 or n).

The Three-Element Boundary Pattern:

For problems needing both left and right boundaries (rectangles, water):

Why It Works: Monotonic property ensures the element below the popped one is always a valid boundary - it's the nearest element in that direction satisfying the condition (smaller for increasing, larger for decreasing).