StackEasy

Valid Parentheses

StackEasy

Step 1 of 8 · Understand

1. Understand the problem

Given a string made up of brackets — (, ), {, }, [, ] — determine whether all the brackets are correctly matched and properly nested.

Input

A string `s` containing only the characters `(`, `)`, `{`, `}`, `[`, `]`.

Output

A boolean — `true` if every opening bracket is closed by the correct type in the right order, `false` otherwise.

Examples

input → s = "()"

output → true

input → s = "()[]{}"

output → true

Three separate valid pairs, none nested.

input → s = "(]"

output → false

The open paren is closed by a bracket — wrong type.

input → s = "([)]"

output → false

The brackets are interleaved incorrectly — [ is closed before ( is closed.

1. Understand the problem

Given a string made up of brackets — (, ), {, }, [, ] — determine whether all the brackets are correctly matched and properly nested.

Input

A string `s` containing only the characters `(`, `)`, `{`, `}`, `[`, `]`.

Output

A boolean — `true` if every opening bracket is closed by the correct type in the right order, `false` otherwise.

Examples

input → s = "()"

output → true

input → s = "()[]{}"

output → true

Three separate valid pairs, none nested.

input → s = "(]"

output → false

The open paren is closed by a bracket — wrong type.

input → s = "([)]"

output → false

The brackets are interleaved incorrectly — [ is closed before ( is closed.

2. Brute force idea

Repeatedly scan the string and remove any directly-adjacent matched pair (like '()' or '[]'). Keep doing this until either the string is empty (valid) or you can't find any more pairs to remove (invalid).

Brute force — the slow one

O(n²)

while '()' in s or '[]' in s or '{}' in s:
    s = s.replace('()', '')    # ← repeated scans and replacements
    s = s.replace('[]', '')
    s = s.replace('{}', '')

return s == ''

Why this is too slow

Each replacement pass is O(n) and you may need up to O(n) passes in the worst case — giving O(n²) total. The string also gets reallocated on every replacement.

Why this is not ideal for interviews

This approach works but it doesn't show understanding of the underlying pattern. Interviewers expect you to recognize that the last-opened bracket must be the first-closed — that's the LIFO behavior of a stack, and it solves this problem in a single O(n) pass.

Time: O(n²)

Space: O(n)

3. Spot the pattern

Before any code, every problem starts with a question. For the Stack pattern, that question is:

“Can I use a stack to remember what's been opened so I can verify each closing bracket matches the most recent opener?”

Matching pairs where 'the last thing opened must be the first thing closed' is the classic stack signal. Stacks are LIFO — last in, first out — which maps perfectly onto bracket nesting.

5. The optimized approach

Walk through the string once. Push opening brackets onto a stack. When you hit a closing bracket, check if the stack's top is the matching opener — if yes, pop; if no (or stack is empty), return false. At the end, the stack should be empty.

Pseudocode

stack = []
pairs = {')': '(', ']': '[', '}': '{'}

for c in s:
    if c in '([{':
        stack.push(c)
    else:                            # c is a closing bracket
        if not stack or stack[-1] != pairs[c]:
            return false
        stack.pop()

return stack is empty

6. Dry run, row by row

Trace it with the first example — s = "()".

step	char	action	stack after
1	(	push	['(']
2	[	push	['(', '[']
3	]	pop '['	['(']
4	)	pop '('	[]
5	—	end of string	empty

step 1: Opening bracket — push it.

step 2: Another opener — push.

step 3: Closing bracket. Top is '[' which matches ']' — pop.

step 4: Closing bracket. Top is '(' which matches ')' — pop.

step 5: Stack is empty — return true.

8. Review & common mistakes

Common mistakes

Not checking whether the stack is empty before peeking
When you hit a closing bracket, always check `stack.length > 0` (or `bool(stack)` in Python) before looking at the top. If the stack is empty, there's no matching opener — that's an immediate false.
Forgetting to check the stack is empty at the end
A string like '((' passes every bracket check — each opener pushes fine — but the stack still has two unmatched openers at the end. Always verify `stack.length === 0` before returning true.
Using a counter instead of a stack
A single counter works for a single bracket type, but breaks with mixed types. '([)]' has balanced counts but isn't valid. You need the stack to track *which* bracket type is currently open.

Try next (when these problems ship)

Min Stack
Valid Palindrome

Ready to go deeper?

Unlock 10 more problems covering Sliding Window, Binary Search, Linked Lists, Trees, and more — same guided format, same hint ladder, one-time $10.

See all problems →

Write your solution above and hit Run tests. Results and tips appear here.

Valid Parentheses

1. Understand the problem

1. Understand the problem

2. Brute force idea

3. Spot the pattern

4. Climb the hint ladder

5. The optimized approach

6. Dry run, row by row

7. The code

8. Review & common mistakes