Stack
Matching, parsing and the monotonic stack family.
5 notes · 23 min total
Questions0 of 32 done
Warm up with these before Phase 1.
Patterns
- 1Matching, Undo & Design StacksUse a stack when the latest unresolved item decides what comes next: matching, undo, collisions, and stacks with extra state.5 min
- 2Expression ParsingEvaluate postfix and infix expressions, decode nested strings and simplify paths with a stack that holds pending work.4 min
- 3Monotonic Stack: Next Greater/SmallerFind the next greater or smaller element for every position in O(n) by popping items the moment they get their answer.5 min
- 4Monotonic Stack: Contribution, Span & AreaUse a monotonic stack to find how far each element reaches left and right, then sum its contribution, span or rectangle area.5 min
- 5Monotonic Stack for Greedy ChoicesBuild the smallest result greedily by popping a worse top whenever a better item arrives, as in Remove K Digits and the 132 pattern.4 min