AlgoViz
HomeStack

Balanced Paranthesis

Easy

Push openers, match on close

Problem

Given a string of brackets ()[]{}, return whether they are balanced and correctly nested.

In simple words

Push opens onto a stack; each close must match the most recent open you pop.

The idea

Push every opening bracket and, on a closing one, check that the top of the stack is its partner and pop it. The stack naturally enforces the nesting order, and a balanced string leaves it empty at the end.

The trick

  • A closing bracket with an empty stack is an immediate failure.
  • Do not forget the final emptiness check — '(((' passes every step otherwise.
  • O(n) time, O(n) space.
(
[
{
}
]
)
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:
Every bracket closes in the right order.

Example 2

Input:
s = "(]"
Output:
false
Explanation:
A round open with a square close → false.

Example 3

Input:
s = "([)]"
Output:
false
Explanation:
Crossed brackets aren't balanced.

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

Finished the walkthrough? Add it to your streak.