Stack
Use last-in-first-out order when the latest unfinished item must be resolved first.
0 of 3 problems solved
Stack
Use last-in-first-out order when the latest unfinished item must be resolved first.
- •Does a closing symbol need to match the latest opening symbol?
- •Would last-in-first-out behavior help?
- •Should I push openings and pop on matching closings?
Valid Parentheses is the cleanest stack problem because the rule is brutally simple: the last thing you opened must be the first thing you close. A stack models that perfectly. Every opening bracket goes on top, and every closing bracket must match the current top. If the order breaks, the whole string breaks.
You are not matching all brackets. You are matching the most recent unfinished one.
- 1Push opening brackets onto the stack.
- 2When you see a closing bracket, check the top of the stack.
- 3If the top matches, pop it. If it does not, return false.
- 4At the end, the stack must be empty for the string to be valid.
Only counting how many brackets appear is not enough. The order matters, and the stack is what preserves that order.
Min Stack
Push pairs: (value, current minimum at this depth). Every push records the minimum so pop never needs to search.
Largest Rectangle in Histogram
Monotonic increasing stack. When a shorter bar arrives, pop taller bars and calculate their rectangle: width is current index minus new stack top minus 1.