Stack algorithms.
Track the top, preserve the invariant, then put it into code.
Stack foundations
Valid Parentheses
Match every closing bracket with the most recent opening bracket.
Min Stack
Store the minimum alongside each value for constant-time queries.
Queue Using Two Stacks
Reverse incoming values only when the outgoing stack is empty.
Expressions & parsing
Evaluate Reverse Polish Notation
Pop the right operand before the left operand, then push the result.
Infix to Postfix
Use an operator stack to respect precedence and parentheses.
Decode a Repeated String
Save an outer prefix and repetition count whenever a nested group begins.
Simplify Unix Path
Resolve dot and parent segments with a stack of directory names.
Remove Adjacent Duplicates
Cancel equal neighbors and let newly adjacent characters meet.
Monotonic stacks
Next Greater Element
Resolve waiting indices when a strictly greater value arrives.
Next Greater Element in a Circular Array
Scan twice to let unresolved positions wrap around once.
Next Smaller Element
Resolve waiting indices when a strictly smaller value arrives.
Daily Temperatures
Use index differences to measure the wait for a warmer day.
Stock Span
Remove dominated prices to find the previous strictly greater price.
Areas & contributions
Largest Rectangle in a Histogram
A smaller bar fixes the right boundary of rectangles waiting on the stack.
Maximal Rectangle in a Binary Matrix
Build a histogram for each row, then solve its largest rectangle.
Trapping Rain Water with a Stack
Pop a valley floor when a right wall appears.
Sum of Subarray Minimums
Charge every subarray minimum to exactly one index.
Simulation & greedy
Asteroid Collision
Resolve only a right-moving survivor meeting a left-moving asteroid.
Remove K Digits
Remove larger preceding digits to make the earliest positions as small as possible.
Longest Valid Parentheses
Keep a boundary index beneath unmatched openings to measure valid suffixes.