Valid Parentheses

Approach Summary

Push open brackets. On close bracket, check if top of stack is the matching open bracket.

Full Solution & Approach

Bracket matching is inherently stack-shaped: the most recently opened bracket must be closed first (LIFO). Iterate through the string. For every opening bracket — ( [ or { — push it onto the stack. For every closing bracket, the top of the stack must be its matching opener; if the stack is empty or the top does not match, the string is invalid. If it matches, pop. At the end the string is valid only if the stack is empty — leftover openers mean something was never closed. Using a dictionary that maps each closing bracket to its opener turns the match check into a single lookup. This runs in one pass with O(1) operations per character, so O(n) total.

Single pass with each bracket pushed once and popped at most once — O(n) time. The stack grows to at most n for a string of only openers — O(n) space.

Solution Code

Solution

def is_valid(s: str) -> bool:
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in pairs:
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()
        else:
            stack.append(ch)
    return not stack

function isValid(s) {
  const pairs = {')': '(', ']': '[', '}': '{'};
  const stack = [];
  for (const ch of s) {
    if (pairs[ch]) {
      if (stack.pop() !== pairs[ch]) return false;
    } else {
      stack.push(ch);
    }
  }
  return stack.length === 0;
}

public boolean isValid(String s) {
    Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
    Deque<Character> stack = new ArrayDeque<>();
    for (char ch : s.toCharArray()) {
        if (pairs.containsKey(ch)) {
            if (stack.isEmpty() || stack.pop() != pairs.get(ch)) return false;
        } else {
            stack.push(ch);
        }
    }
    return stack.isEmpty();
}

bool isValid(const string& s) {
    unordered_map<char,char> pairs = {{')','('},{']','['},{'}','{'}};
    vector<char> stack;
    for (char ch : s) {
        if (pairs.count(ch)) {
            if (stack.empty() || stack.back() != pairs[ch]) return false;
            stack.pop_back();
        } else {
            stack.push_back(ch);
        }
    }
    return stack.empty();
}

Edge Cases to Watch

Empty string — valid (return true)
Starts with a closing bracket — the stack is empty, immediately false
Ends with an opener — the stack is non-empty at the end, false
Mismatched nesting like "([)]" — the top-of-stack check catches it

How to Recognize This Pattern

Bracket matching
Nested structure validation

Complexity Analysis

Time Complexity

O(n)

Space Complexity