Valid Parentheses Solutions & Complexity

1. Define the problem

Valid Parentheses

You are given a string s made only of the characters ( ) [ ] { }. Decide whether the string is balanced . Balanced means every opening bracket is closed later by the matching closing bracket, and brackets never cross over each other. "([])" is balanced. "([)]" is not, because the round bracket closes while the square bracket is still open. Use a stack to remember the opening brackets you have seen but not closed yet. Every closing bracket must match the most recent unclosed opening bracket, which is exactly the item sitting on top of the stack. The string is valid when you never hit a mismatch and the stack ends up empty .

Constraints

1 ≤ s.length ≤ 10⁴
s contains only the characters '(', ')', '[', ']', '{' and '}'
The answer is true or false

Example

Inputs = "([])"

Outputtrue

Explanation The round bracket opens, the square bracket opens and closes inside it, then the round bracket closes. Nothing crosses, so the string is balanced.

2. Know the words first

In plain terms

Stack: A pile of items where you can only add to the top and only remove from the top, like a stack of plates. The last thing you put in is the first thing you take out.
Push: Putting one new item on top of the stack.
Pop: Taking the top item off the stack and looking at it. The stack gets one shorter.
Balanced: Every opening bracket has a matching closing bracket of the same kind, in the right order, with nothing crossing over.

3. Visualize the solution

The row below is the stack, bottom-left to top-right

0—

1—

2—

3—

Statusinit

Start with an empty stack before reading any character of "([])".

What happens in this step

s = "([])"
stack = [] (every slot shows a dash)

Nothing has been read yet, so there is no unclosed bracket to remember.

Step 1 of 6

Steps to visualize

The row of cells is the stack itself. Cell 0 is the bottom, and the last filled cell is the top.
A dash means that slot is empty right now.
Read the string one character at a time. An opening bracket is pushed on top of the stack.
A closing bracket pops the top item off and checks that the two form a matching pair.
If the pair never mismatches and the stack ends empty, the string is balanced.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

The row below is the stack, bottom-left to top-right

0—

1—

2—

3—

Statusinit

Start with an empty stack before reading any character of "([])".

What happens in this step

s = "([])"
stack = [] (every slot shows a dash)

Nothing has been read yet, so there is no unclosed bracket to remember.

Step 1 of 6

5. Solution

Solution

solution.tsTypeScript

function isValid(s) {
  const pairs = { ')': '(', ']': '[', '}': '{' };
  const stack = [];

  for (const ch of s) {
    if (ch === '(' || ch === '[' || ch === '{') {
      stack.push(ch);
      continue;
    }

    if (stack.pop() !== pairs[ch]) {
      return false;
    }
  }

  return stack.length === 0;
}

Time: O(n)
Space: O(n)

6. Test cases

Test cases

Input	Expected	Covers
`s = "([])"`	`true`	example from the description
`s = "()[]{}"`	`true`	three separate pairs side by side
`s = "([)]"`	`false`	brackets that cross over each other
`s = "("`	`false`	smallest input, one bracket left open
`s = "]"`	`false`	a closing bracket with an empty stack
`s = "{[()()]}"`	`true`	several levels of nesting

Valid Parentheses