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 ParenthesesMatch open/close brackets with stackeasy
- 2.Min StackAuxiliary stack for O(1) getMin()medium
- 3.Evaluate Reverse Polish NotationPush operands, pop on operatormedium
- 4.Daily TemperaturesMonotonic decreasing stack storing indexesmedium
- 5.Next Greater Element IMonotonic stack + Hash Mapeasy
- 6.Next Greater Element IIMonotonic stack over 2x array lengthmedium
- 7.Largest Rectangle in HistogramMonotonic increasing stack storing heights/indexeshard
- 8.Car FleetSort by position + stack time to targetmedium
- 9.Decode StringStack for multipliers & nested stringsmedium
- 10.Remove K DigitsMonotonic stack build smallest numbermedium
- 11.Asteroid CollisionStack collision simulationmedium
- 12.Simplify PathSplit path by slash + stack for dir/..medium
- 13.Basic CalculatorStack for operators & sign +/-hard
- 14.Basic Calculator IIStack for * and / precedencemedium
- 15.Score of ParenthesesStack nesting score computationmedium
Also Important
10 more questions worth practicing.
- 16.Backspace String CompareSimulate backspaces with stackeasy
- 17.Baseball GameRecord scores with stackeasy
- 18.Remove All Adjacent Duplicates In StringPop duplicate adjacent characterseasy
- 19.Make The String GreatPop upper/lower case pairseasy
- 20.Online Stock SpanMonotonic stack store price & span countmedium
- 21.Exclusive Time of FunctionsCall stack execution timingmedium
- 22.Validate Stack SequencesSimulate push and pop sequencesmedium
- 23.Remove Duplicate LettersMonotonic stack + char count & visited setmedium
- 24.Sum of Subarray MinimumsMonotonic stack previous/next smallermedium
- 25.Maximum Width RampMonotonic 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
Last In โ First Out
Analogy: Stack of platesTop item is pushed last and popped first.
First In โ First Out
Analogy: People standing in lineFront item is pushed first and popped first.
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
Accessing stack[len(stack)-1] without checking len(stack) > 0 causes array index out-of-range panic.
For problems like Daily Temperatures where distance matters, store indexes on the stack, not just values.
One new large element can resolve multiple smaller unresolved elements. Use a while len(stack) > 0 && current > top loop!
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 (
appendand 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."