Valid parentheses

You walk into an Amazon phone screen and the interviewer starts with a classic warm-up: "Given a string of brackets, tell me if they're properly matched." This problem, commonly known as Valid Parentheses, appears in interviews at Bloomberg, Amazon, and Facebook because it cleanly tests whether you understand stacks, hash maps, and careful edge-case handling in a single short exercise.

TL;DR

Use a stack paired with a hash map that maps each opening bracket to its closing counterpart. For every opening bracket, push the expected closing bracket onto the stack. For every closing bracket, pop from the stack and verify a match. After processing every character, return true only if the stack is empty. This runs in O(n) time and O(n) space.

Why This Problem Matters

Valid parentheses is one of the most frequently asked stack problems in technical interviews. It introduces the pattern of using a stack to enforce ordering constraints, which shows up in expression evaluation, HTML/XML tag matching, compiler syntax validation, and many other scenarios. Mastering this pattern here makes those harder problems far more approachable.

Understanding the Problem

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

1. Every opening bracket is closed by the same type of bracket
2. Brackets are closed in the correct order

checkValid("()[]()") -> true
checkValid("(())")   -> true
checkValid("([)]")   -> false

Edge Cases

1. Empty string: Valid (nothing to violate the rules)
2. Single bracket: Always invalid (no matching pair)
3. Only opening brackets: Invalid (stack will not be empty at the end)
4. Interleaved brackets: ([)] is invalid even though each bracket type appears twice

Solution Approach

The key insight is that brackets must close in reverse order of how they opened. The most recently opened bracket must close first. This is exactly what a stack provides: last-in, first-out ordering.

The algorithm works in three parts:

1. Map each opening bracket to its expected closing bracket
2. Push the expected closing bracket onto a stack when you see an opening bracket
3. Pop and compare when you see a closing bracket

Here is how the stack evolves for the valid input ([]):

Each opening bracket pushes its matching closer. Each closing bracket pops from the stack and confirms a match. At the end, the stack is empty, so the string is valid.

Now compare with the invalid input ([)], where brackets are interleaved:

After pushing ) and ], the next character is ). But the top of the stack is ], not ). The mismatch causes an immediate return of false.

Implementation

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

import java.util.Deque;
import java.util.LinkedList;
import java.util.Map;

public class Solution {
  public Boolean checkValid(String str) {
    Map<Character, Character> openClosePairs =
      Map.of('(', ')', '[', ']', '{', '}');
    Deque<Character> stack = new LinkedList<>();
    for (char c : str.toCharArray()) {
      if (openClosePairs.containsKey(c)) stack.push(openClosePairs.get(c));
      else if (stack.isEmpty() || (!stack.pop().equals(c)))
        return false;
    }
    return stack.isEmpty();
  }
}

Let's walk through the code:

1. Create a bracket map: Map.of('(', ')', '[', ']', '{', '}') maps each opener to its closer
2. Initialize a stack: Deque<Character> serves as a LIFO stack
3. Iterate through each character: For opening brackets, push the expected closer. For closing brackets, pop and compare.
4. Final check: Return stack.isEmpty() to catch unclosed opening brackets like "(("

Here is how the stack processes a more complex valid input, {()[]}:

Multiple bracket types nest correctly. Each closer matches the most recent opener, and the stack empties cleanly by the end.

Complexity Analysis

Time: O(n) where n is the string length. Each character triggers exactly one stack operation (push or pop), and both operations are O(1). The hash map lookup is also O(1) with a constant number of bracket types.

Space: O(n) in the worst case. A string like (((( pushes one element per character. In the best case, the very first character is a closing bracket with an empty stack, and you return false using O(1) space.

Why Not Use a Counter?

For a single bracket type like (), you could track balance with a counter: increment on (, decrement on ), reject if it goes negative. But with three bracket types, a counter cannot detect ordering violations. The string ([)] has equal counts of each type yet is invalid. A stack captures both count and order.

Common Pitfalls

1. Forgetting the final empty check: Processing "((" never triggers a mismatch during iteration, but the stack is not empty afterward. Always return stack.isEmpty(), not true.

2. Checking for the opening bracket instead of the closing bracket: If you push the opening bracket onto the stack, you need an extra map lookup when comparing. Pushing the expected closer simplifies the comparison to a single equality check.

3. Missing the empty-stack guard: When you encounter a closing bracket, check stack.isEmpty() before calling stack.pop(). A string like "]" has no matching opener, and popping an empty stack throws an exception.

Interview Tips

When presenting this solution:

• Mention by name that this is a stack problem. Interviewers want to hear you recognize patterns.
• Explain why you push the closing bracket rather than the opening bracket. It shows you thought about design tradeoffs.
• Walk through both a valid and invalid example to demonstrate the algorithm handles both paths.
• Note the two failure modes: mismatch during iteration and non-empty stack at the end.
• If asked for follow-ups, mention generating all valid parentheses combinations (a backtracking problem) or handling additional characters mixed in with brackets.

Key Takeaways

• A stack enforces last-in-first-out ordering, which naturally matches how brackets nest. Push the expected closer, pop and compare when you see a closer.
• The hash map provides O(1) lookup from opening bracket to closing bracket, keeping the solution clean and extensible to additional bracket types.
• Two separate checks are required: mismatches during iteration and a non-empty stack at the end. Missing either one produces incorrect results.
• This problem appears frequently at Bloomberg, Amazon, and Facebook. It is often used as a warm-up that sets the tone for harder stack or recursion questions.
• The O(n) time and O(n) space solution is optimal. You must examine every character, and the stack can grow linearly in the worst case.

Practice and Related Problems

Once you are comfortable with bracket matching, try these progressions:

• Minimum number of bracket reversals to balance a string
• Longest valid parentheses substring
• Generate all combinations of n pairs of valid parentheses

This problem and hundreds of others are available on Firecode, where consistent daily practice helps you build the pattern recognition that top tech companies look for. Whether you are warming up for phone screens or preparing for on-site interviews, starting with fundamentals like this sets you up well.

Solutions in Other Languages

Python

class Solution:
    def check_valid(self, s: str) -> bool:
        open_close_pairs = {
            '(': ')',
            '[': ']',
            '{': '}'
        }
        stack = []
        for c in s:
            if c in open_close_pairs:
                stack.append(open_close_pairs[c])
            elif len(stack) == 0 or stack.pop() != c:
                return False
        return len(stack) == 0

JavaScript

class Solution {
  checkValid(str) {
    const openClosePairs = new Map([['(', ')'], ['[', ']'], ['{', '}']]);
    const stack = [];
    for (let i = 0; i < str.length; i++) {
      const c = str.charAt(i);
      if (openClosePairs.has(c)) stack.push(openClosePairs.get(c));
      else if (stack.length === 0 || stack.pop() !== c) return false;
    }
    return stack.length === 0;
  }
}

TypeScript

class Solution {
    checkValid(str: string): boolean {
        const openClosePairs = new Map<string, string>([['(', ')'], ['[', ']'], ['{', '}']]);
        const stack: string[] = [];
        for (let i = 0; i < str.length; i++) {
            const c = str.charAt(i);
            if (openClosePairs.has(c)) stack.push(openClosePairs.get(c)!);
            else if (stack.length === 0 || stack.pop() !== c) return false;
        }
        return stack.length === 0;
    }
}

C++

#include <iostream>
#include <stack>
#include <unordered_map>

class Solution {
public:
  bool checkValid(const std::string &str) {
    std::unordered_map<char, char> openClosePairs = {
        {'(', ')'},
        {'[', ']'},
        {'{', '}'}};
    std::stack<char> stk;
    for (char c: str) {
      if (openClosePairs.count(c))
        stk.push(openClosePairs[c]);
      else {
        if (stk.empty() || stk.top() != c)
          return false;
        stk.pop();
      }
    }
    return stk.empty();
  }
};

Go

package solution

func (s *Solution) CheckValid(str string) bool {
    openClosePairs := map[rune]rune{'(': ')', '[': ']', '{': '}'}
    stack := NewStack()
    for _, c := range str {
        if _, ok := openClosePairs[c]; ok {
            stack.Push(openClosePairs[c])
        } else if stack.IsEmpty() || stack.Pop() != c {
            return false
        }
    }
    return stack.IsEmpty()
}

Scala

import scala.collection.mutable

class Solution {
  def checkValid(str: String): Boolean = {
    val openClosePairs = Map('(' -> ')', '[' -> ']', '{' -> '}')
    val stack: mutable.Stack[Char] = mutable.Stack()
    for (c <- str.toCharArray) {
      if (openClosePairs.contains(c)) stack.push(openClosePairs(c))
      else if (stack.isEmpty || stack.pop != c) return false
    }
    stack.isEmpty
  }
}

Kotlin

class Solution {
    fun checkValid(str: String): Boolean {
        val openClosePairs = mapOf('(' to ')', '[' to ']', '{' to '}')
        val stack = ArrayDeque<Char>()
        for (c in str) {
            if (openClosePairs.containsKey(c)) {
                stack.addFirst(openClosePairs[c]!!)
            } else if (stack.isEmpty() || stack.removeFirst() != c) {
                return false
            }
        }
        return stack.isEmpty()
    }
}

Swift

class Solution {
    func checkValid(_ str: String) -> Bool {
        let openClosePairs: [Character: Character] = ["(": ")", "[": "]", "{": "}"]
        var stack = [Character]()
        for c in str {
            if let closing = openClosePairs[c] {
                stack.append(closing)
            } else if stack.isEmpty || stack.removeLast() != c {
                return false
            }
        }
        return stack.isEmpty
    }
}

Rust

impl Solution {
    pub fn check_valid(&self, s: String) -> bool {
        let open_close_pairs: HashMap<char, char> =
            [('(', ')'), ('[', ']'), ('{', '}')].into();
        let mut stack: Vec<char> = Vec::new();
        for c in s.chars() {
            if let Some(&closing) = open_close_pairs.get(&c) {
                stack.push(closing);
            } else if stack.pop() != Some(c) {
                return false;
            }
        }
        stack.is_empty()
    }
}

C#

using System.Collections.Generic;

public class Solution {
    public bool checkValid(string str) {
        var openClosePairs = new Dictionary<char, char> {
            {'(', ')'},
            {'[', ']'},
            {'{', '}'}
        };
        var stack = new Stack<char>();
        foreach (char c in str) {
            if (openClosePairs.ContainsKey(c)) stack.Push(openClosePairs[c]);
            else if (stack.Count == 0 || stack.Pop() != c)
                return false;
        }
        return stack.Count == 0;
    }
}

Dart

class Solution {
  bool checkValid(String str) {
    Map<String, String> openClosePairs = {'(': ')', '[': ']', '{': '}'};
    List<String> stack = [];
    for (String c in str.split('')) {
      if (openClosePairs.containsKey(c)) {
        stack.add(openClosePairs[c]!);
      } else if (stack.isEmpty || stack.removeLast() != c) {
        return false;
      }
    }
    return stack.isEmpty;
  }
}

PHP

class Solution {
    public function checkValid(string $str): bool {
        $openClosePairs = ['(' => ')', '[' => ']', '{' => '}'];
        $stack = [];
        foreach (str_split($str) as $char) {
            if (isset($openClosePairs[$char])) {
                $stack[] = $openClosePairs[$char];
            } elseif (empty($stack) || array_pop($stack) !== $char) {
                return false;
            }
        }
        return empty($stack);
    }
}

Ruby

class Solution
  def check_valid(str)
    open_close_pairs = { '(' => ')', '[' => ']', '{' => '}' }
    stack = []
    str.each_char do |c|
      if open_close_pairs.key?(c)
        stack.push(open_close_pairs[c])
      elsif stack.empty? || stack.pop != c
        return false
      end
    end
    stack.empty?
  end
end