RTE logo
← Back to DSA map
Stack

Valid Parentheses

Are the brackets in a string properly opened and closed?

Easy

Problem

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

  • Open brackets must be closed by the same type.
  • Open brackets must be closed in the correct order.
  • Every closing bracket has a matching opening bracket.

Examples

Input: s = "()[]{}"
Output: true
Input: s = "(]"
Output: false
( is closed by ].
Input: s = "([)]"
Output: false
The order is wrong.
Input: s = "{[]}"
Output: true

Approach

Time O(n)Space O(n)
  1. Keep a stack of open brackets and a map from each opener to its closer.
  2. Push every opening bracket.
  3. For a closing bracket, pop the top. If the stack was empty or the popped opener does not match, the string is invalid.
  4. At the end the stack must be empty - leftovers are openers that were never closed.

Common mistakes

  • Returning true at the end without checking the stack is empty accepts "((".
  • Counting brackets per type misses order: "([)]" has balanced counts but is invalid.

Step through it

Pick an input and play the algorithm step by step. The highlighted line in the code follows each step, and you can edit the code to experiment.

STACK
Solution · JS
String · i=— ch=—
(0
)1
STACK[ ]
matching info appears here
Index
—
Char
—
Stack
0
Need
—
Valid
—
0 / 0
1×
Execution log
steps appear here…

Solution

The same approach in JavaScript, Python, and Java. Each is a complete program that prints the examples above - JavaScript runs here, so edit it and try your own input.

Edit and run it here

JavaScript solution

Loading...

Output

Run code to see output...

Comments

Sign in to leave a comment. Your name and photo come from Google; nothing else is shared.

Loading comments...