Bracket Harmony Check: validate nested brackets with a stack

You're twenty minutes into a Google phone screen when the interviewer says, "Given a string of brackets, tell me if every open bracket has a matching close." It sounds simple enough, but then they add: "Oh, and you have three types of brackets." This is Bracket Harmony Check, also known as Valid Parentheses on other platforms. It's one of the most frequently asked easy problems across the industry, appearing regularly at companies like Google, Amazon, Adobe, Meta, and Bloomberg.

TL;DR

Use a stack. Walk through the string one character at a time. When you see an opening bracket, push it. When you see a closing bracket, pop the stack and check if the popped bracket matches. If the stack is empty when you need to pop, or the popped bracket doesn't match, return false. After processing all characters, return true only if the stack is empty.

The Problem

Given a string s containing only the characters (, ), {, }, [, and ], determine whether the string is valid.

A valid string satisfies three conditions:

1. Every opening bracket is closed by the same type of bracket.
2. Brackets are closed in the correct order.
3. Every closing bracket has a corresponding opening bracket.

isValid("()")     => true
isValid("()[]{}")  => true
isValid("(]")     => false
isValid("([])")   => true

Why a Counter Falls Short

Your first instinct might be to count brackets. If the number of opening brackets equals the number of closing brackets, the string is valid, right? Not quite. Consider ([)]. Both ( and [ have their matching closers present, but the nesting is wrong: the ] tries to close [ before ) closes (.

This is where order matters. Bracket validation is fundamentally about nesting, and nesting implies a last-in, first-out access pattern. That points directly to a stack.

The Stack Approach

The algorithm is straightforward:

1. Create an empty stack.
2. For each character in the string:
   • If it's an opening bracket ((, {, [), push it onto the stack.
   • If it's a closing bracket, check if the stack is empty (if so, return false). Pop the top element and verify it matches the closing bracket. If not, return false.
3. After processing all characters, return true only if the stack is empty.

Walking Through a Valid Case

Take the input ([]). Here's how the stack evolves:

Each opening bracket gets pushed, and each closing bracket pops its matching opener. The stack ends empty, so the string is valid.

Detecting a Mismatch

Now consider (]. The opening ( gets pushed, but when we encounter ], we pop ( and find it doesn't match ]:

The mismatch is caught immediately when the popped element doesn't correspond to the closing bracket.

Nested Brackets

For deeper nesting like {[()]}, the stack grows to three elements before unwinding:

Each closing bracket pops the most recent unmatched opener, and the LIFO property of the stack guarantees the correct matching order.

Crossed Brackets

The input ({) looks almost valid, but the brackets cross rather than nest properly:

When ) arrives, the top of the stack is {, not (. The mismatch triggers an immediate false return.

Edge Cases

Two edge cases deserve attention.

Extra closing bracket: A closing bracket with no matching opener. The stack is empty when we try to pop.

Unmatched openers: All opening brackets, no closers. The stack is not empty after processing.

Both cases are handled by the same two checks: "is the stack empty when we need to pop?" and "is the stack empty at the end?"

Implementation

Prefer a different language? Jump to solutions in other languages.

import java.util.*;

public class Solution {
  public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();

    for (char c : s.toCharArray()) {
      if (c == '(' || c == '{' || c == '[') {
        stack.push(c);
      } else {
        if (stack.isEmpty()) {
          return false;
        }
        char top = stack.pop();
        if ((c == ')' && top != '(') ||
            (c == '}' && top != '{') ||
            (c == ']' && top != '[')) {
          return false;
        }
      }
    }

    return stack.isEmpty();
  }
}

A few implementation notes:

• The Java solution uses explicit character comparisons rather than a hash map. For only three bracket types, direct comparison is clear and avoids the overhead of map lookups.
• The Python solution below uses a dictionary mapping closers to openers, which is more idiomatic for that language. Both approaches are correct.
• The stack.isEmpty() check before popping prevents EmptyStackException when a closing bracket has no corresponding opener.

Complexity Analysis

Time: O(n)

Each character is visited exactly once. Push and pop are O(1) operations, so the total work is proportional to the string length.

Space: O(n)

In the worst case, every character is an opening bracket (e.g., (((((), and all of them end up on the stack. The best case is O(1) when the first character triggers an immediate mismatch.

There's no way to improve on O(n) time since every character must be inspected at least once. The O(n) space is also necessary because the stack must track all unmatched openers, and a string of all openers is a valid input.

Common Mistakes

1. Forgetting the empty-stack check before popping. If the string starts with ), popping an empty stack throws an exception. Always check stack.isEmpty() first.

2. Returning true when the loop finishes without checking the stack. A string like ((( passes through the loop without errors but leaves three unmatched brackets on the stack.

3. Using a counter instead of a stack. As discussed earlier, counters can't detect ordering violations like ([)].

4. Mapping brackets in the wrong direction. If your map goes from openers to closers, you need to look up the popped opener in the map and compare its value to the current closer. If your map goes from closers to openers, you compare the map's value to the popped element. Mixing these up causes silent wrong answers.

Interview Tips

When this problem comes up in an interview:

• State the approach early. "I'll use a stack to track unmatched opening brackets." This tells the interviewer you recognize the pattern.
• Mention why a counter fails. Bringing up ([)] as a counterexample shows you've thought about the problem beyond the happy path.
• Talk through the three termination conditions: mismatch on pop, empty stack on pop, and non-empty stack at the end. These cover all failure modes.
• Discuss the map vs. direct comparison tradeoff. A map scales better if you add more bracket types, but direct comparison is fine for three types.

Related Patterns

Valid Parentheses is the gateway to a family of stack-based problems:

• Generate Parentheses (backtracking to produce all valid combinations)
• Longest Valid Parentheses (dynamic programming or stack to find the longest valid substring)
• Wildcard Parenthesis Validator (handling * as wildcard open, close, or empty)
• Min Add to Make Parentheses Valid (counting the minimum insertions)
• Score of Parentheses (scoring nested bracket depth)

The stack pattern from this problem carries directly into all of them. Once you're comfortable with the push/pop/check rhythm here, extending it to more complex variants becomes a matter of adjusting what you store on the stack and how you process each character.

Want to build that muscle memory? Firecode serves these problems in a spaced repetition sequence, so you practice each pattern right when you're about to forget it. Over 50,000 engineers have used it to prepare for interviews at top tech companies.

Solutions in Other Languages

Python

The Python solution uses a dictionary to map closing brackets to their openers, and a # sentinel for empty-stack pops.

class Solution:
    def is_valid(self, s: str) -> bool:
        stack = []
        bracket_map = {')': '(', '}': '{', ']': '['}

        for char in s:
            if char in bracket_map:
                top_element = stack.pop() if stack else '#'
                if bracket_map[char] != top_element:
                    return False
            else:
                stack.append(char)

        return not stack

JavaScript

class Solution {
  isValid(s) {
    const stack = [];
    const bracketMap = {
      '(': ')',
      '{': '}',
      '[': ']'
    };

    for (let char of s) {
      if (bracketMap[char]) {
        stack.push(char);
      } else {
        const top = stack.pop();
        if (bracketMap[top] !== char) {
          return false;
        }
      }
    }

    return stack.length === 0;
  }
}

TypeScript

class Solution {
  isValid(s: string): boolean {
    const stack: string[] = [];
    const bracketMap: Record<string, string> = {
      '(': ')',
      '{': '}',
      '[': ']'
    };

    for (const char of s) {
      if (bracketMap[char]) {
        stack.push(char);
      } else {
        const top = stack.pop();
        if (bracketMap[top!] !== char) {
          return false;
        }
      }
    }

    return stack.length === 0;
  }
}

C++

#include <stack>
#include <unordered_map>

class Solution {
public:
  bool isValid(std::string &s) {
    std::stack<char> stack;
    std::unordered_map<char, char> matchingBrackets = {
      {')', '('},
      {'}', '{'},
      {']', '['}
    };

    for (char c : s) {
      if (c == '(' || c == '{' || c == '[') {
        stack.push(c);
      } else {
        if (stack.empty() || stack.top() != matchingBrackets[c]) {
          return false;
        }
        stack.pop();
      }
    }

    return stack.empty();
  }
};

Go

func (sol *Solution) IsValid(s string) bool {
    stack := []rune{}
    matchingBrackets := map[rune]rune{
        ')': '(',
        '}': '{',
        ']': '[',
    }

    for _, char := range s {
        if char == '(' || char == '{' || char == '[' {
            stack = append(stack, char)
        } else if char == ')' || char == '}' || char == ']' {
            if len(stack) == 0 || stack[len(stack)-1] != matchingBrackets[char] {
                return false
            }
            stack = stack[:len(stack)-1]
        }
    }

    return len(stack) == 0
}

Scala

class Solution {
  def isValid(s: String): Boolean = {
    val stack = scala.collection.mutable.Stack[Char]()
    val matchingBrackets = Map(')' -> '(', '}' -> '{', ']' -> '[')
    val openingBrackets = Set('(', '{', '[')

    for (char <- s) {
      if (openingBrackets.contains(char)) {
        stack.push(char)
      } else if (matchingBrackets.contains(char)) {
        if (stack.isEmpty || stack.pop() != matchingBrackets(char)) {
          return false
        }
      }
    }
    stack.isEmpty
  }
}

Kotlin

import java.util.*

class Solution {
  fun isValid(s: String): Boolean {
    val stack = ArrayDeque<Char>()

    for (c in s) {
      if (c == '(' || c == '{' || c == '[') {
        stack.addLast(c)
      } else {
        if (stack.isEmpty()) {
          return false
        }
        val top = stack.removeLast()
        if ((c == ')' && top != '(') ||
            (c == '}' && top != '{') ||
            (c == ']' && top != '[')) {
          return false
        }
      }
    }
    return stack.isEmpty()
  }
}

Swift

import Foundation

class Solution {
    func isValid(_ s: String) -> Bool {
        var stack = [Character]()

        for c in s {
            if c == "(" || c == "{" || c == "[" {
                stack.append(c)
            } else {
                if stack.isEmpty {
                    return false
                }
                let top = stack.removeLast()
                if (c == ")" && top != "(") ||
                   (c == "}" && top != "{") ||
                   (c == "]" && top != "[") {
                    return false
                }
            }
        }
        return stack.isEmpty
    }
}

Rust

impl Solution {
    pub fn is_valid(s: String) -> bool {
        let mut stack: Vec<char> = Vec::new();

        for c in s.chars() {
            if c == '(' || c == '{' || c == '[' {
                stack.push(c);
            } else {
                if stack.is_empty() {
                    return false;
                }
                let top = stack.pop().unwrap();
                if (c == ')' && top != '(')
                    || (c == '}' && top != '{')
                    || (c == ']' && top != '[')
                {
                    return false;
                }
            }
        }
        stack.is_empty()
    }
}

C#

using System.Collections.Generic;

public class Solution {
    public bool IsValid(string s) {
        var stack = new Stack<char>();

        foreach (char c in s) {
            if (c == '(' || c == '{' || c == '[') {
                stack.Push(c);
            } else {
                if (stack.Count == 0) {
                    return false;
                }
                char top = stack.Pop();
                if ((c == ')' && top != '(') ||
                    (c == '}' && top != '{') ||
                    (c == ']' && top != '[')) {
                    return false;
                }
            }
        }
        return stack.Count == 0;
    }
}

Dart

class Solution {
  bool isValid(String s) {
    List<String> stack = [];

    for (String c in s.split('')) {
      if (c == '(' || c == '{' || c == '[') {
        stack.add(c);
      } else {
        if (stack.isEmpty) {
          return false;
        }
        String top = stack.removeLast();
        if ((c == ')' && top != '(') ||
            (c == '}' && top != '{') ||
            (c == ']' && top != '[')) {
          return false;
        }
      }
    }
    return stack.isEmpty;
  }
}

PHP

class Solution {
    public function isValid(string $s): bool {
        $stack = [];

        foreach (str_split($s) as $char) {
            if ($char === '(' || $char === '{' || $char === '[') {
                $stack[] = $char;
            } else {
                if (empty($stack)) {
                    return false;
                }
                $top = array_pop($stack);
                if (($char === ')' && $top !== '(') ||
                    ($char === '}' && $top !== '{') ||
                    ($char === ']' && $top !== '[')) {
                    return false;
                }
            }
        }
        return count($stack) === 0;
    }
}

Ruby

class Solution
  def is_valid(s)
    stack = []

    s.each_char do |c|
      if c == '(' || c == '{' || c == '['
        stack.push(c)
      else
        return false if stack.empty?
        top = stack.pop
        if (c == ')' && top != '(') ||
           (c == '}' && top != '{') ||
           (c == ']' && top != '[')
          return false
        end
      end
    end
    stack.empty?
  end
end