Valid Parentheses
Valid Parentheses is LeetCode 20 (Easy). You are given a string s made only of the six bracket characters (, ), [, ], { and }. Return true if the brackets are balanced and false otherwise.
A string counts as valid only when all three rules hold:
- Same type: every opening bracket is closed by a bracket of the same type.
- Right order: brackets close in the reverse of the order they opened, so pairs nest and never cross.
- Nothing unmatched: every closing bracket has an opening bracket before it, and no opening bracket is still open at the end.
The string can be up to 10⁴ characters long, so the check should be one linear pass.
- 1 <= s.length <= 10⁴
- s consists of parentheses only '()[]{}'.
Intuition
Valid parentheses is a question about nesting. In {[()]} the ( opened last, so it must close first; the { opened first, so it closes last. The most recent unclosed bracket is always the next one to close.
That rule is exactly last in, first out, which is what a stack does. Each opener goes on top as the new innermost bracket, each closer must match the top, and a string is balanced only if nothing is left open at the end. Counting brackets is not enough: ([)] opens and closes one of each type, yet the pairs cross, and only the stack knows which bracket is innermost.
Any time a later symbol has to match the most recent unmatched earlier symbol, reach for the balanced parentheses stack pattern: brackets, HTML tags, nested function calls, undo operations. With only one bracket type a single counter would do; several types need the stack to remember the order.
Approach
Before reading on, list the three different ways a bracket string can be invalid, and say which line of your code catches each one. Aim for O(n) time.
Map each closer to its opener
Store pairs = { ')': '(', ']': '[', '}': '{' }. Keying by the closer means one lookup answers both questions: is this a closer? and which opener does it need?
Scan the string once
- Opener (not a key in
pairs) – push it. - Closer with a non-empty stack whose top equals
pairs[ch]– pop. - Closer otherwise – return
falseat once.
The first closer that meets the wrong top, or an empty stack, already proves the string invalid, so there is no reason to keep scanning.
Check what is left
After the loop, return true only if the stack is empty. Anything still on it is an opener that was never closed; a string of only openers passes every closer check, so this final test is the only thing that catches it.
Why the stack is correct
A valid string can be reduced to empty by repeatedly deleting an adjacent pair like (). The stack performs exactly those deletions in left-to-right order: each pop removes an innermost pair. If a closer ever meets the wrong top, no sequence of deletions can fix it, because the bracket in between can never be removed first.
Valid Parentheses solution in Python | C++ | Java
([)]. Return false without reading further.not stack, not simply true once the loop ends.stack is non-empty before looking at the top is what stops this from crashing; the answer is false immediately.Common pitfalls
Returning true as soon as the loop ends
for ch in s:
...
return Truefor ch in s:
...
return not stack"((" never hits a mismatch, so the loop finishes cleanly. The leftover openers on the stack are the only sign it is invalid.
Reading the top of an empty stack
elif stack[-1] == pairs[ch]:
stack.pop()elif stack and stack[-1] == pairs[ch]:
stack.pop()")" or "())" reach a closer with nothing open. Without the emptiness check this raises an IndexError in Python and is undefined behaviour in C++.
Complexity
Valid Parentheses FAQ
How do you check valid parentheses using a stack?
- Data structure: a stack of opening brackets, plus a map from each closer to its opener.
- Opener: push it.
- Closer: if the stack is empty or its top is not the matching opener, return
false; otherwise pop. - End: return
trueonly if the stack is empty. - Complexity: O(n) time, O(n) space.
- Example:
"{[()]}"pushes{ [ (, then pops them in reverse order and ends empty, so it is valid.
How is the stack written in the valid parentheses Python solution?
A plain list: append pushes, pop() removes the top and stack[-1] peeks at it. not stack is true when it is empty, which is both the guard before peeking and the final answer.
Can valid parentheses be solved without a stack?
With only one bracket type, a counter works: add 1 for (, subtract 1 for ), fail if it goes negative, and require 0 at the end. With several types a counter cannot see crossings like ([)], so some form of stack is needed.
What are the ways a parentheses string can be invalid?
Three: a closer of the wrong type ((]), a closer with nothing open ()(), and openers left unclosed at the end (((). The first two are caught inside the loop; the third only by checking the stack is empty afterwards.
What is the time and space complexity of LeetCode 20?
O(n) time, because each character is pushed and popped at most once. O(n) space in the worst case, when every character is an opening bracket.