Stack · LC #20
Valid Parentheses
Determine whether a string of brackets is properly nested and closed in the correct order. Teaches the canonical stack pattern for matching open/close pairs.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given a string `s` containing `(`, `)`, `{`, `}`, `[`, `]`, return `true` if the input string is valid. Open brackets must be closed by the same type and in the correct order. An empty string is considered valid.
Sample I/O
Input: s = "()[]{}"
Output: true
Input: s = "(]"
Output: false
Input: s = "([)]"
Output: falseTime: O(n) · Space: O(n)
Intuition
How to Think About It
Intuition
A stack naturally mirrors bracket nesting: push openers, and each closer must match the most recent unclosed opener on top. Any mismatch or leftover openers at the end signals invalidity. The LIFO property enforces the correct nesting order automatically.
Core Concept
Iterate the string character by character. Push every opening bracket onto the stack. For each closing bracket, check that the stack is non-empty and that the top element is the corresponding opener - if not, return false immediately. After the loop the stack must be empty; any remaining openers were never closed.
When to use
Anytime you need to validate or parse nested/paired delimiters: HTML/XML tags, arithmetic expressions, compiler token streams, config file syntax validation.
When NOT to use
Single bracket type with no nesting (simple counter suffices). When you need to report line/column of the error rather than a boolean (augment with index tracking). Non-bracket matching problems where pairs are not adjacent in a LIFO sense.
Key Insights
What to Know Cold
- Use a mapping from closer → opener to avoid three separate if-statements.
- Always check `stack.isEmpty()` before popping - an unmatched closer on an empty stack is invalid.
- Final `stack.isEmpty()` check catches unclosed openers like `"(("`.
- Push the matching opener rather than the close char to simplify the comparison.
- Empty string is trivially valid because the stack is empty after zero iterations.
1 example
Worked Examples
Mixed bracket validation
Input `"()[]{}"` - three separate valid pairs.
Each opener is pushed; each closer matches the top and pops it. Stack is empty at end → valid.
isValid("()[]{}"); // true - each pair resolves cleanly
isValid("([)]"); // false - inner pair crosses outer pairOutput: true / false
Demonstrates that the stack enforces LIFO ordering - interleaved pairs like `([)]` are correctly rejected even though each individual pair has a match somewhere in the string.