Valid Parentheses

Difficulty: Easy

Problem

The string s contains only the six characters '(', ')', '{', '}', '[' and ']'. Decide whether the brackets are balanced: (1) every opening bracket is closed by a bracket of the same type, (2) closings come in the right order, so the most recently opened bracket is closed first, and (3) no closing bracket appears without a matching opening one.

Example

Input: s = "({[]})"
Output: true
Explanation: Each opening bracket is closed by its matching bracket in the correct order: [ ] is matched, then { } wraps it, then ( ) wraps everything.

Brute-force approach

Repeatedly scan the string and remove adjacent matching pairs '()', '[]', '{}' until no more can be removed. If the string becomes empty, it's valid.

Steps

  1. While the string contains '()', '[]', or '{}':
  2. Replace all occurrences of '()', '[]', '{}' with empty string
  3. If the string is now empty, return true
  4. Otherwise return false

Time complexity: O(n²) · Space complexity: O(n)

Trade-offs

  • Each pass through the string is O(n), and we may need up to n/2 passes
  • String replacement creates new strings each time
  • Inefficient for long strings with deeply nested brackets

Optimal approach

Key insight: The last opened bracket must be the first one closed. A perfect fit for a stack's LIFO behavior.

Use a stack: push opening brackets, and for each closing bracket check if it matches the top of the stack. If all match and the stack is empty at the end, the string is valid.

Steps

  1. Create a map: ')' → '(', ']' → '[', '}' → '{'
  2. Initialize an empty stack
  3. For each character in the string:
  4. If closing bracket: check stack top matches, pop if yes, return false if no
  5. If opening bracket: push onto stack
  6. Return true if stack is empty, false otherwise

Time complexity: O(n) · Space complexity: O(n)

Pseudocode

function isValid(s):
    stack = []
    map = { ')': '(', '}': '{', ']': '[' }
    
    for each char in s:
        if char is a closing bracket:
            if stack is empty or stack.top != map[char]:
                return false
            stack.pop()
        else:
            stack.push(char)
    
    return stack is empty

Hints

  • Use a stack to keep track of opening brackets
  • When you encounter a closing bracket, the top of the stack must be the matching opening bracket
  • At the end, the stack must be empty for the string to be valid

Complexity questions

What is the time complexity of the repeated pair-removal approach?

O(n²). Each pass scans the string in O(n) and we may need up to O(n) passes in the worst case, giving O(n²).

What is the time complexity of the stack-based approach?

O(n). We traverse the string once, doing O(1) push/pop per character. Total: O(n).

What is the worst-case space for the stack approach?

O(n). In the worst case (all opening brackets like '((((('), the stack holds all n characters → O(n).

Check your understanding of Valid Parentheses

Is the string '()[]{}' valid?

Yes, each opening bracket has a matching closing bracket in the correct order. '()[]{}' is valid because each opening bracket is immediately closed by its matching type. They don't need to be nested, sequential pairs are also valid.

Is the string '(' valid?

No, every opening bracket must have a corresponding closing bracket. A string is only valid if every opening bracket is eventually closed by a matching bracket. '(' has no closing ')' so it's invalid.

For input '([)]', why is the answer false even though all brackets have matches?

Because brackets must be nested properly, not just paired, ( must close before [ does. In '([)]', the [ is opened inside (, so ] must come before ). The interleaving '([)]' violates proper nesting order.

Related problems

Keep practising