Valid Parentheses
Decide whether a string of brackets ()[]{} is opened and closed in the correct order.
Progress cannot be saved in this browser, so completed lessons will reset when you leave.
Lesson notes
Try it before you watch
Restate the problem in your own words, list the edge cases, and sketch a solution with its running time. Then play the video and compare.
Reveal the key idea
Push opening brackets onto a stack. Each closing bracket must match the top of the stack, and the string is valid only if the stack ends up empty.
Pattern: Stacks & heaps. Stacks match the most recent item; heaps keep the smallest or largest item one pop away.
Complexity
| Measure | Bound |
|---|---|
| Time | O(n) |
| Extra space | O(n) |
Walkthroughs often start from a simpler approach first; aim to reach these bounds. New to Big-O? Read understanding algorithmic complexity.