Valid Parentheses
Decide whether brackets close in the correct type and order.
Why does this pattern fit?
Restate the exact job
Decide whether brackets close in the correct type and order.
A closing bracket must match the newest unmatched opening bracket.
O(n) time · O(n) space
Checking only total counts ignores nesting order.
How to solve Valid Parentheses
The goal is to solve this problem from the pattern, not to memorize a finished answer. Use this as a check after your own attempt.
What the question asks
Decide whether brackets close in the correct type and order.
Why Stacks fits
A closing bracket must match the newest unmatched opening bracket.
State to maintain
A stack of expected closing brackets.
Transition
Push the expected closer for each opener; every closer must equal the stack top.
Time and space
O(n) time · O(n) space
Counterexample to the tempting mistake
Checking only total counts ignores nesting order.
Prove it again tomorrow
Close this page. Rebuild the state and transition from memory, write a test that exposes the mistake above, then solve a fresh input without looking back. A same-day reread is practice, not proof of retention.