AlgoViz
HomeStack

Valid Parentheses

Easy

Openers wait on a stack for their match

In simple words

Every time you open a bracket, remember it; each closing bracket must match the most recent opener.

The idea

Push every opening bracket. On a closing bracket, the top of the stack must be the matching opener — otherwise it's invalid. A clean run leaves the stack empty.

(
[
{
}
]
)
0
1
2
3
4
5
stack[]

Step 1 of 9. Push every opening bracket. On a closer, the top of the stack must be its match. Values: (, [, {, }, ], ). stack [].

1/9
Optimal
timeO(n)spaceO(n)

Match closers against the top.

1// openers wait on a stack for their match2const stack = [], pair = { ')': '(', ']': '[', '}': '{' };3for (const c of s) {4  if (!(c in pair)) stack.push(c);5  else {6    if (stack.pop() === pair[c]) continue;7    return false;8  }9}10return stack.length === 0;

Input

array
[(, [, {, }, ], )]

Memory

i
—
stack
[]

Output

stack
[]
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
s = "()"
Output:
true
Explanation:
A simple matched pair.

Example 2

Input:
s = "()[]{}"
Output:
true
Explanation:
Three matched pairs in a row.

Example 3

Input:
s = "(]"
Output:
false
Explanation:
Mismatched bracket types → false.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.