Loading…
Valid Parentheses is a easy coding interview question covering stack, strings — the kind asked at FAANG (Facebook/Meta, Apple, Amazon, Netflix, Google) and AI-first companies like Anthropic, OpenAI, and Nvidia.
Given a string `s` containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if: open brackets are closed by the same type of brackets, in the correct order, and every close bracket has a corresponding open bracket.
Try it yourself first
In an interview you'd get about 15 minutes for a easy question. Sketch an approach before peeking — struggling is where the learning happens.
Stuck? Reveal them one at a time — each hint gives away a little more.
Ready to compare notes? The full solution, visualization, and complexity analysis are below.
Input string: ( { [ ] } )
Stack (top →)
Variables
| 1 | def is_valid(s): |
| ▶ | stack = [] |
| 3 | pairs = {')': '(', '}': '{', ']': '['} |
| 4 | for char in s: |
| 5 | if char in '([{': |
| 6 | stack.append(char) |
| 7 | elif char in ')]}': |
| 8 | if not stack or stack[-1] != pairs[char]: |
| 9 | return False |
| 10 | stack.pop() |
| 11 | return len(stack) == 0 |
Initialize empty stack. We'll push opening brackets and pop when we see their matching closers.
Time
O(n)
Space
O(n)
Count each bracket type with three counters
O(n) time, O(1) space
Genuinely O(1) space, and genuinely wrong. Counting is blind to nesting order, so it accepts '([)]' - the counts balance perfectly while the structure does not. It is only correct when there is a single bracket type.
Repeatedly delete '()', '[]' and '{}' until the string stops changing
O(n^2) time, O(n) space
It does produce the right answer, and it is a nice one-liner in Python. But each pass rebuilds the whole string, so it is quadratic - fine for a puzzle, not for the interview version of this question.
Use a stack. Iterate the string: push open brackets; for close brackets, check if the top of the stack is the matching opener. Return true if the stack is empty at the end.
A full interview loop is more than one round. These are the others, each with what is on the site for it.