Valid Parentheses

You are given a string s that contains only the six bracket characters (, ), [, ], { and }. Decide whether its brackets are properly balanced.

The string is balanced when all of the following hold:

• every opening bracket is closed by a closing bracket of the same kind;
• brackets close in the reverse order of opening, so a pair that starts inside another pair must also end inside it;
• no closing bracket appears without an unmatched opening bracket before it.

Return true if s is balanced and false otherwise.

Example 1

Example 2

Example 3

Constraints

• 1 <= s.length <= 104
• s consists only of the characters ()[]{}.

Pattern Path · Stacks · problem 42 of 169

Start simple

Repeatedly delete adjacent matching pairs such as "()" until the string stops changing, then check whether it is empty: O(n²) time.

The key idea

The key observation is that a closing bracket can only ever match the most recently opened bracket that is still unmatched. Anything opened earlier is wrapped around it and has to wait. That last-in, first-out order is exactly what a stack gives you.

Scan the string once. Push each opening bracket. When a closing bracket arrives, look at the top of the stack:

• if the stack is empty, nothing is waiting to be closed, so the string is invalid;
• if the top is a different kind of bracket, the pairs cross (as in [(])), so the string is invalid;
• otherwise pop it: that pair is finished.

After the scan, any brackets left on the stack were never closed, so the string is valid only if the stack is empty. A small map from each closer to its opener keeps the matching logic to a single comparison.

Complexity

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

Python

class Solution:
    def isValid(self, s):
        partner = {')': '(', ']': '[', '}': '{'}
        stack = []
        for ch in s:
            if ch in partner:
                # A closer must match the most recent unmatched opener.
                if not stack or stack.pop() != partner[ch]:
                    return False
            else:
                stack.append(ch)
        # Anything left over was opened but never closed.
        return not stack

JavaScript

var isValid = function(s) {
  const partner = { ')': '(', ']': '[', '}': '{' };
  const stack = [];
  for (const ch of s) {
    if (ch in partner) {
      // A closer must match the most recent unmatched opener.
      if (stack.length === 0 || stack.pop() !== partner[ch]) return false;
    } else {
      stack.push(ch);
    }
  }
  // Anything left over was opened but never closed.
  return stack.length === 0;
};

What the interviewer is checking

The interviewer wants to see you recognise nested, last-opened-first-closed structure and map it to a stack, while handling the empty-stack and leftover-opener cases cleanly.

Mistakes to avoid

• Forgetting the final check that the stack is empty, which wrongly accepts strings like "((".
• Popping from an empty stack when the string starts with a closer such as "]".
• Counting each bracket type separately: counts alone accept crossed pairs like "[(])".

Follow-ups to expect

• What if the string can also contain letters and digits? (Skip every non-bracket character.)
• With only one kind of bracket, can you use O(1) space? (A single depth counter suffices.)
• How would you report where the first error occurs? (Store indices on the stack.)

In real software

Compilers, code editors and JSON or XML parsers use this stack check to match delimiters, highlight the partner of a bracket and point at the first unbalanced one.

Practice next