Valid Parentheses

Try It Yourself

Use the editor below to validate the order and type of every closing symbol. Store opening symbols until their matching closing symbols arrive.

Submit your implementation when it passes the examples. Check incorrect nesting, extra opening symbols, and a closing symbol with no opener.

Valid Parentheses

easyStack · Strings20 minLC 20

Problem

Given a string containing only parentheses, brackets, and braces, return true when every opening symbol is closed by the same type in the correct order.

An empty stack at the end means every opening symbol was matched.

Example 1:

Input: s = "()[]{}"

Output: true

Example 2:

Input: s = "([)]"

Output: false

Constraints

1 ≤ s.length ≤ 10,000
s contains only ()[]{}.

0 attempts

Solution

Push every opening symbol onto a stack. For a closing symbol, pop the most recent opener and verify that it is the required matching type.

Return false immediately for a mismatch or an empty stack. At the end, the stack must also be empty.

function isValidParentheses(s) {
  const expectedOpening = new Map([
    [")", "("],
    ["]", "["],
    ["}", "{"],
  ]);
  const stack = [];

  for (const symbol of s) {
    if (!expectedOpening.has(symbol)) {
      stack.push(symbol);
      continue;
    }

    if (stack.pop() !== expectedOpening.get(symbol)) {
      return false;
    }
  }

  return stack.length === 0;
}

Big O notation

Measure	Complexity	Explanation
Time	`O(n)`	Every symbol is inspected and pushed or popped at most once.
Auxiliary space	`O(n)`	An input containing only opening symbols fills the stack.