Valid Parentheses — Stack Bracket Matching for FAANG Interviews

Problem Statement#

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

A string is valid if every open bracket is closed by the same type of bracket, open brackets are closed in the correct order, and every close bracket has a corresponding open bracket.

Constraints:

• 1 <= s.length <= 10^4
• s consists of parentheses only: ()[]{}.

Input:  s = "()"
Output: true

Input:  s = "()[]{}"
Output: true

Input:  s = "(]"
Output: false
Explanation: The closing bracket ] does not match the open bracket (.

Why This Problem Matters#

LeetCode 20 is one of the most frequently asked warm-up problems at Google, Meta, Amazon, and Microsoft. It is deliberately simple so the interviewer can observe how you think before the real challenge begins.

The reason interviewers love Valid Parentheses: the solution is a textbook demonstration of the LIFO (Last-In, First-Out) property of stacks. Any time you have matching pairs that must close in reverse order — brackets, HTML tags, function calls, undo history — a stack is the canonical data structure.

Getting this problem wrong under pressure — mishandling the empty-stack case, forgetting to check stack.isEmpty() at the end — signals poor attention to edge cases. Getting it right fluently signals clean thinking. Interviewers frequently follow this with variants like "now do it with recursion," "what if the string also contains letters you should ignore," or "how many insertions are needed to make it valid?" Knowing the stack insight makes those variants trivial.

Companies that ask this problem: Google, Meta, Amazon, Microsoft, Bloomberg, Uber, LinkedIn, Apple.

The Core Insight#

Every close bracket must match the most recently seen open bracket. That is exactly what a stack gives you: the most recently pushed element is at the top.

The key algorithmic decisions:

1. For every character in s:
   • If it is an open bracket, push it onto the stack.
   • If it is a close bracket, check whether the stack top is the matching open bracket. If not, or if the stack is empty, return false.
2. After the loop, the string is valid only if the stack is empty — every open bracket was matched.

Using a hash map {')': '(', ']': '[', '}': '{'} expresses the matching relationship cleanly without a chain of if/elif statements. The map key is the close bracket; the value is the expected open bracket on the stack top.

Visual Dry Run#

Input: s = "{[()]}"

Stack is empty → return true.

Input: s = "([)]"

Solution (Optimal)#

# Python — O(n) time, O(n) space
def isValid(s: str) -> bool:
    # Map each closing bracket to its expected opening bracket
    matching = {')': '(', ']': '[', '}': '{'}
    stack = []                          # holds unmatched open brackets
 
    for ch in s:
        if ch in matching:              # it is a closing bracket
            # Stack must be non-empty and top must be the matching open bracket
            if not stack or stack[-1] != matching[ch]:
                return False
            stack.pop()                 # consume the matched open bracket
        else:
            # It is an open bracket — push for future matching
            stack.append(ch)
 
    # Valid only if every open bracket was matched (stack is empty)
    return not stack

// JavaScript — O(n) time, O(n) space
function isValid(s) {
    // Map each closing bracket to its expected opening bracket
    const matching = { ')': '(', ']': '[', '}': '{' };
    const stack = [];
 
    for (const ch of s) {
        if (ch in matching) {               // it is a closing bracket
            if (!stack.length || stack[stack.length - 1] !== matching[ch]) {
                return false;
            }
            stack.pop();
        } else {
            // It is an open bracket — push for future matching
            stack.push(ch);
        }
    }
 
    return stack.length === 0;
}

Complexity:

Common Mistakes#

1. Not checking for empty stack before popping. A string like "]" has no open bracket. Popping from an empty stack crashes or returns wrong results. Always guard with if not stack before accessing stack[-1].

2. Forgetting to check stack.isEmpty() at the end. The string "(" never closes — the loop ends without error but the stack is non-empty, so it must return false. Many candidates forget this final check.

3. Building the map backwards. Mapping '(' -> ')' instead of ')' -> '(' means you look up using the open bracket, which is the wrong direction at decision time. The map key must be the close bracket.

4. Checking only the last character. Some candidates try if s[-1] in matching without using a stack, missing interleaved invalid cases like ([)].

5. Using == on Character objects in Java. In Java, char comparisons are fine as primitives, but boxing to Character and using == compares references. Use .equals() or unbox to char.

Interview Tips#

• State the LIFO insight out loud: "Close brackets must match the most recently opened bracket, which is exactly what the stack top gives me."
• Mention the edge cases proactively: empty string (returns true), single bracket, all open brackets, all close brackets.
• When asked about O(1) space: it is only possible for a single bracket type. With a single bracket type you can use a counter — increment on open, decrement on close, fail if counter goes negative or ends non-zero.
• If asked for the recursive approach: treat each matching pair as a recursive subproblem; the call stack essentially simulates the explicit stack.

Follow-up Questions#

1. What if the string contains letters? Skip non-bracket characters; only act on ([{})].
2. Minimum insertions or deletions to make valid? Classic stack problem — count unmatched opens and closes separately.
3. Wildcards: * can be (, ), or empty? LC 678 — track a range of possible open-bracket counts with lo and hi counters.
4. Minimum number of bracket reversals? Count mismatches and use ceiling division.
5. Remove the minimum invalid parentheses? LC 301 — BFS over all possible removal combinations or a stack-based greedy approach.

Key Takeaways#

• A stack is the correct data structure whenever a closing element must match the most recent opening element — the LIFO property directly models nesting.
• Use a hash map from close-to-open bracket to express matching in O(1) without if/elif chains.
• Two non-obvious edge cases: empty stack when a close bracket arrives (unmatched close), and non-empty stack after the loop (unmatched open).
• The same pattern powers Decode String (LC 394), Score of Parentheses (LC 856), and Minimum Remove to Make Valid Parentheses (LC 1249).
• This problem is a warm-up in FAANG interviews; the interviewer is watching for clean code, edge-case awareness, and how you communicate the LIFO insight.
• O(1) space is only achievable for single bracket types using a counter; mixed bracket types fundamentally require a stack.