Stack
How Stack works
Why it matters
Parsers, editors, and configuration loaders must reject malformed nesting before it causes a misleading downstream error. Repeatedly deleting matched text rescans deeply nested input again and again. For "([]{})", verify in one pass that every closing bracket matches the most recent unmatched opening bracket.
Real-world constraint
Brackets in your editor
When your editor highlights the bracket that closes the one under your cursor, or a compiler reports an unclosed brace, a stack is doing the work. The parser pushes each opening token and pops it when the matching close arrives. Undo follows the same rule: each edit is pushed, and undo pops the most recent one.
Example
Valid Parentheses
s contains only '()', '[]', and '{}'. Return true if the brackets are balanced and correctly nested.
- Input
- s = "([]{})"
- Output
- True
Approach 2 · Resolve the bottleneck
The idea
Keep one example in view
Valid Parentheses
s = "([]{})"→True
The baseline, Delete matched pairs until none are left, is O(n²) · O(n). The better model below keeps this exact input and removes that bottleneck.
In "([]{})", "]" must close "[" before ")" can close "(". Rather than rescan and delete adjacent pairs over multiple rounds, keep unfinished opening brackets in a stack so the required match is available immediately.
Read "([]{})" from left to right. Push "(", then push "[" above it. When "]" arrives, pop "[" and compare the pair. The earlier "(" stays unfinished underneath.
Next push "{" and pop it for "}". The final ")" pops "(". A Python list supplies append and pop in O(1), so each bracket enters and leaves at most once. The empty stack at the end proves that no opening bracket was left unmatched.
Pro
The rest of this is on Pro
The idea above is free. The walkthrough, the cost, and the practice are on Pro.