visual walkthrough
Valid Parentheses
The canonical stack question; often the first problem in a phone screen.
The idea
Brackets nest: the last one opened must be the first one closed. That is exactly what a stack does. Push each opener; when a closer arrives it must match the opener on top.
At the end the stack must be empty, otherwise some opener was never closed.
Complexity
| approach | time | space |
|---|---|---|
| Delete matching pairs | O(n²) | O(n) |
| Stack | O(n) | O(n) |