Given a string containing only the characters ()[]{}, return whether it is valid: every opening bracket is closed by the same type of bracket, and brackets close in the correct order.
Before you code
Counting each type of bracket isn't enough: ([)] has one of each but is invalid. What matters is which opener is the most recent one still open.
Hints
- Push each opener onto a stack.
- For each closer, the stack must be non-empty and its top must be the matching opener; pop it.
- A map from closer to opener keeps the check to one line.
- At the end, the stack must be empty:
"(("has no mismatch but leaves openers unclosed.
Production & complexity notes
When solving Valid parentheses on LeetCode (easy), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Stacks and the LIFO rule to reinforce the underlying pattern.
What it practices
Using a stack for nested structure, from Stacks and the LIFO rule.