Valid Parentheses

Given a string s containing only the characters '(', ')', '{', '}', '[' and ']', determine whether it is valid.

A string is valid when every open bracket is closed by the same type of bracket, brackets close in the correct order, and every bracket has a matching partner.

Hints

· Stuck? Reveal one nudge at a time.

When you see a closing bracket, which open bracket must it match?

It can only match the most recently opened, still-unmatched bracket — that's a stack.

Push openers; on a closer, check the top of the stack is its partner, then pop.

Common doubts

Counts alone can't catch wrong nesting: '([)]' has balanced counts but closes in the wrong order. A stack enforces that a closer matches the nearest open bracket.

A closer when the stack is empty, a closer whose top is the wrong type, or leftover openers at the end (a non-empty stack).

Unmatched openers like in '(((' never trigger a mismatch during the scan; the only place they're caught is the final empty check.

Interview follow-ups

· What an interviewer asks next.

Ignore any character that isn't a bracket — only push/pop on the six bracket symbols.

When a mismatch or empty-pop happens, return the current index; if the scan finishes, the first leftover opener's index is the offending one.

Fun facts

Bracket matching is the classic motivating example for stacks and is at the heart of every parser and compiler front-end.
The 'delete adjacent pairs until stable' view connects to formal-language reductions and Dyck words in combinatorics.

Asked at

AmazonGoogleMicrosoftMeta

Frequently Sometimes Occasionally

Example 1

Input: s = "()[]{}"
Output: true
Each pair opens and closes correctly in order.

Example 2

Input: s = "([)]"
Output: false
The brackets close in the wrong order: ')' arrives while '[' is still open.

Constraints

- 1 <= s.length <= 10^4 - s consists only of the characters '()[]{}'.

A closing bracket can only match the bracket that was opened most recently and is still unclosed. That "most recent unmatched" rule is exactly last-in-first-out — a stack. Push every opener; on a closer, the top of the stack must be its partner, or the string is invalid.

Prerequisites

Before you start

· Concepts used directly in the solution.

Stacks. Last-in-first-out access — the top is always the most recently pushed item.

Bracket matching. Each closer has exactly one opener type it can pair with.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Validity rules

“Does a closer have to match the bracket type?”

Yes — ( must be closed by ), [ by ], { by }.

“Does nesting order matter?”

Yes — ([)] is invalid even though counts match, because the closers arrive in the wrong order.

Edges

“Is a leftover open bracket valid?”

No — every opener must eventually be matched, so a non-empty stack at the end means invalid.

The ideal opening — say it like this

A closing bracket can only pair with the most recently opened, still-unmatched bracket.

That's a stack: I push every opener and, on a closer, check the top is its matching opener.

If the top doesn't match or the stack is empty I fail; at the end the stack must be empty.

Understand the problem

Worked example — s = "{[]}"

{  push        stack: {
[  push        stack: { [
]  top is [ ✓  pop    stack: {
}  top is { ✓  pop    stack: (empty)
end, stack empty -> valid

Key observations

1Aha

A closer matches the nearest open

Correct nesting means the most recently opened bracket must be the first to close. That last-in-first-out discipline is precisely a stack.

2Aha

Three ways to be invalid

A closer with an empty stack (nothing to match), a closer whose top is the wrong type (mismatched pair), or leftover openers at the end (unmatched) all make the string invalid.

3Aha

One pass, stack of openers

Each character is pushed or popped at most once, so a single left-to-right pass with an opener stack decides validity in linear time.

Brute force vs optimal

	Delete pairs repeatedly	Stack
Idea	Erase '()','[]','{}' until nothing changes	Push openers, match each closer against the top
Time	O(n^2)	O(n)
Space	O(n)	O(n)

Repeatedly deleting matched pairs works but rescans the string each round; the stack matches every bracket in a single pass. Full code is in the Approaches selector below.

Summary

Key takeaway

Push openers onto a stack; for each closer, the top must be its matching opener (else invalid). A valid string ends with an empty stack. The "match the nearest open" rule is last-in-first-out — one linear pass.

stack = []
for ch in s:
    if ch is an opener: push ch
    else:
        if stack empty or top != matching opener of ch: return false
        pop
return stack is empty