Pattern #15

Stack

Important interview questions, thinking patterns, monotonic stack techniques, and rules for solving stack problems in Go.

Must Solve

15 core questions — solve these first.

1.Valid Parentheses
Match open/close brackets with stackeasy
2.Min Stack
Auxiliary stack for O(1) getMin()medium
3.Evaluate Reverse Polish Notation
Push operands, pop on operatormedium
4.Daily Temperatures
Monotonic decreasing stack storing indexesmedium
5.Next Greater Element I
Monotonic stack + Hash Mapeasy
6.Next Greater Element II
Monotonic stack over 2x array lengthmedium
7.Largest Rectangle in Histogram
Monotonic increasing stack storing heights/indexeshard
8.Car Fleet
Sort by position + stack time to targetmedium
9.Decode String
Stack for multipliers & nested stringsmedium
10.Remove K Digits
Monotonic stack build smallest numbermedium
11.Asteroid Collision
Stack collision simulationmedium
12.Simplify Path
Split path by slash + stack for dir/..medium
13.Basic Calculator
Stack for operators & sign +/-hard
14.Basic Calculator II
Stack for * and / precedencemedium
15.Score of Parentheses
Stack nesting score computationmedium

Also Important

10 more questions worth practicing.

16.Backspace String Compare
Simulate backspaces with stackeasy
17.Baseball Game
Record scores with stackeasy
18.Remove All Adjacent Duplicates In String
Pop duplicate adjacent characterseasy
19.Make The String Great
Pop upper/lower case pairseasy
20.Online Stock Span
Monotonic stack store price & span countmedium
21.Exclusive Time of Functions
Call stack execution timingmedium
22.Validate Stack Sequences
Simulate push and pop sequencesmedium
23.Remove Duplicate Letters
Monotonic stack + char count & visited setmedium
24.Sum of Subarray Minimums
Monotonic stack previous/next smallermedium
25.Maximum Width Ramp
Monotonic decreasing index stackmedium

How to Think

Need last item first?Stack (LIFO)
Brackets / parentheses?Stack
Need undo previous thing?Stack
Need next greater / smaller?Monotonic Stack
Need process nested structure (3[a2[c]])?Stack
Need evaluate math expression?Stack

Go Slice as Stack Template

Basic Stack Operations in Go

stack := []int{}

// Push
stack = append(stack, val)

// Top (Peek)
top := stack[len(stack)-1]

// Pop
top = stack[len(stack)-1]
stack = stack[:len(stack)-1]

// Check Empty
isEmpty := len(stack) == 0

👉 Push / Pop / Top are all O(1) time complexity!

Stack vs Queue

Stack (LIFO)

Last In → First Out
Analogy: Stack of plates

Top item is pushed last and popped first.

Queue (FIFO)

First In → First Out
Analogy: People standing in line

Front item is pushed first and popped first.

Visual Memory Rule

Parentheses   → Open: Push | Close: Match & Pop Top
Next Greater  → Monotonic Stack (while current > top -> pop)
Distance      → Store INDEXES on stack (i - stack.Top)

💡 Golden Rule: "If the newest unfinished thing should be handled first, think Stack."

Common Interview Mistakes

1. Popping Empty Stack

Accessing stack[len(stack)-1] without checking len(stack) > 0 causes array index out-of-range panic.

2. Storing Value Instead of Index

For problems like Daily Temperatures where distance matters, store indexes on the stack, not just values.

3. Forgetting Multiple Pops

One new large element can resolve multiple smaller unresolved elements. Use a while len(stack) > 0 && current > top loop!

4. Using Stack When Queue Is Needed

If you need the oldest item processed first, that's a Queue (FIFO), not a Stack (LIFO).

Interview Rules

1. Parentheses? → Stack
2. Undo / Backtracking state? → Stack
3. Nested expression? → Stack
4. Evaluate math expression? → Stack
5. Need last unresolved item? → Stack
6. Next greater/smaller? → Monotonic Stack
7. Distance to next greater? → Store indexes on stack
8. Push / Pop / Peek → O(1) time complexity
9. In Go → Use slice as stack (append and slice truncation)

Small Rules

Rule 1: Main operations Push, Pop, Top/Peek are O(1).
Rule 2: Stack processes items in reverse order (LIFO).
Rule 3: Before popping, always check len(stack) > 0.
Rule 4: For matching brackets, top must match the current closing bracket type.
Rule 5: Store indexes instead of values when distance/position is needed (e.g. Daily Temperatures).

Production Thinking

Undo / Redo → Actions pushed onto stack, undo pops latest action

Browser Navigation → Back button history behaves like a stack of visited URLs

Function Call Stack → LIFO call frames (main -> foo -> bar)

Compilers / Parsers → Nested syntax trees, brackets, and math expressions

Path Processing → Directory traversal `/a/b/../c` (encounter `..` -> pop)

Remember This

Last In            → First Out
Push               → Add top
Pop                → Remove top
Parentheses        → Stack
Nested data        → Stack
Undo               → Stack
Next greater       → Monotonic Stack
Need distance      → Store index

💡 Golden Rule: "If the newest unfinished thing should be handled first, think Stack."