You’re in a coding interview. The interviewer gives you a warm-up: “Given a string of brackets, determine if it’s valid.” You know this is a stack problem. But this is exactly where Easy problems are dangerous: rush through it, skip the final empty-stack check, and your interviewer’s first impression is that you’re careless under pressure.

This walkthrough covers the complete arc: stack-based reasoning, every edge case that trips candidates up, what the ideal solution looks like, and the follow-up problems that interviewers frequently pivot to.

---

The Problem

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

A string is valid if:

• Every open bracket is closed by the same type of closing bracket.
• Open brackets are closed in the correct order.
• Every closing bracket has a corresponding open bracket.

Example

Input s = "()[{}]"

Output true

Each opening bracket is matched by its correct closing bracket, and they are properly nested. A second example: s = "(]" returns false because the ( is closed by ], which is the wrong type. And s = "([)]" returns false because the brackets are interleaved, ( is not closed before [ closes. Order matters as much as type.

Already comfortable with the solution? Practice it in a mock interview →

---

What Interviewers Are Actually Testing

Despite its Easy rating, Valid Parentheses is a precise test of stack intuition. Interviewers use it to see whether you immediately identify that the Last-In-First-Out structure of a stack perfectly models the nesting constraint and whether you can implement it without edge case bugs.

Skill	What Interviewers Observe
Stack recognition	Do you identify the LIFO structure as the natural fit for matching nested brackets?
Data structure justification	Can you explain why a stack works, not just that it does?
Hash map for bracket pairs	Do you use a clean mapping from closing to opening bracket instead of chained conditionals?
Edge case coverage	Do you handle empty string, all openers, all closers, and mismatched types?
Final stack check	Do you remember to return False if the stack is non-empty at the end?
Follow-up readiness	Can you extend to minimum bracket removals, generating valid combinations, or scoring?

---

Step 1: Clarifying Questions

Even for a short, well-scoped problem, asking clarifying questions before coding demonstrates disciplined thinking:

1. Does the string contain only bracket characters, or can it include letters, numbers, or spaces? LeetCode guarantees only bracket characters. If other characters were allowed, you’d need a decision: ignore them or treat them as invalid.

2. Is an empty string considered valid? Yes, an empty string has no unmatched brackets, so it’s trivially valid. This is naturally handled by the stack approach (an empty stack at the end returns True).

3. Can the string be very long? LeetCode allows strings up to 10,000 characters. This confirms O(n) is the target.

4. Should I return a boolean, or indicate which bracket is mismatched? Return a simple True/False. Knowing this prevents over-engineering an error-reporting system that wasn’t asked for.

---

Step 2: A First (Non-Optimal) Idea

The most intuitive first approach: repeatedly remove adjacent valid pairs ((), [], {}) until no more can be removed. If the string becomes empty, it’s valid.

def isValid(s):
    while "()" in s or "[]" in s or "{}" in s:
        s = s.replace("()", "")
        s = s.replace("[]", "")
        s = s.replace("{}", "")
    return s == ""

This is correct but O(n^2) in time: each replacement pass is O(n), and you might need O(n) passes in the worst case. More importantly, it doesn’t model the nesting structure of brackets explicitly. A stack makes the nesting model transparent and runs in O(n).

Approach	Time	Space
Repeated replacement	O(n^2)	O(n)
Stack-based matching	O(n)	O(n)

---

Step 3: The Key Insight

Brackets must close in the reverse order they were opened: last opened, first closed. This is exactly the LIFO behavior of a stack.

As you scan left to right, every opening bracket gets pushed onto the stack. Every closing bracket should match the most recently opened unmatched bracket, the one at the top of the stack. If it matches, pop and continue. If it doesn’t match, or the stack is empty, the string is invalid.

After scanning the entire string, if any opening brackets remain on the stack, they were never closed and the string is invalid.

Three failure modes to name explicitly:

1. Wrong type: A closing bracket doesn’t match the open bracket on top, e.g., (].
2. Stack underflow: A closing bracket arrives when the stack is empty, e.g., ).
3. Unclosed openers: The string ends with opening brackets still on the stack, e.g., ((.

---

Step 4: Optimal Strategy

1. Initialize an empty stack and a mapping matches = {')': '(', ']': '[', '}': '{'}.
2. Iterate through each character c in s:
   • If c is an opening bracket, push it onto the stack.
   • If c is a closing bracket:
     • If the stack is empty, return False.
     • Pop the top. If it doesn’t equal matches[c], return False.
3. After the loop, return True if the stack is empty, False otherwise.

---

Python Implementation

def isValid(s: str) -> bool:
    stack = []

    # Maps each closing bracket to its expected opening bracket
    matches = {')': '(', ']': '[', '}': '{'}

    for char in s:
        if char in matches:
            # It's a closing bracket — check against the top of the stack
            if not stack or stack[-1] != matches[char]:
                return False  # Stack empty (no opener) or wrong type
            stack.pop()
        else:
            # It's an opening bracket — push onto the stack
            stack.append(char)

    # Valid only if all openers have been matched and popped
    return len(stack) == 0

Implementation notes worth calling out in an interview:

• if char in matches cleanly distinguishes closing brackets from opening ones, since matches only contains closing brackets as keys. This avoids a separate if char in "([{" check.
• if not stack or stack[-1] != matches[char] handles both failure cases (empty stack and wrong type) in a single condition. Checking not stack first prevents an IndexError via short-circuit evaluation.
• return len(stack) == 0 is the critical final check. Returning True unconditionally after the loop is one of the most common bugs in this problem.
• The matches dictionary makes the bracket pairing data-driven. Adding a new bracket type (e.g., <>) requires adding a single entry, no logic changes.

---

Time & Space Complexity

Operation	Complexity
Time	O(n)
Space	O(n)

Time: We iterate through the string exactly once. Each character triggers exactly one stack operation (push or pop), both O(1). Total: O(n).

Space: In the worst case (a string of all opening brackets like "(((((") every character is pushed without being popped. Stack grows to O(n).

A common follow-up: “Can you reduce space below O(n)?” For the general case with three bracket types, no. You need to remember all unmatched openers. If the input only uses one type (e.g., ()), you could use a counter instead of a stack, reducing space to O(1).

---

Common Interview Mistakes

1. Forgetting the final empty-stack check. The single most common bug. After the loop, leftover opening brackets mean the string is invalid. Returning True unconditionally produces wrong answers for inputs like "((" or "({[".

2. Not checking for an empty stack before popping. When a closing bracket arrives, verify the stack is non-empty before accessing stack[-1]. An empty stack means there’s no opener to match. Forgetting this causes an IndexError on inputs like ")".

3. Using a chain of if/elif instead of a hash map. Verbose, harder to read, and easy to miscopy one condition. A matches dictionary expresses the same logic in a single lookup.

4. Only checking character count. Counting opening and closing brackets catches some invalid strings but misses mismatched types ("(]") and wrong order ("([)]"). Counting is necessary but not sufficient.

5. Not naming the three failure modes before coding. Candidates who articulate all three failure modes (wrong type, underflow, unclosed openers) before writing code demonstrate genuine understanding rather than pattern recall.

6. Treating this as too simple to explain carefully. Because it’s rated Easy, some candidates rush without communicating reasoning. A fluent, well-explained Easy solution is far more impressive than a silent correct one.

---

What a Strong Candidate Sounds Like

“This is a bracket matching problem, and the key constraint is that brackets must close in the reverse order they were opened: last in, first out. That’s exactly what a stack models.

My approach: scan left to right. Push every opening bracket onto the stack. When I see a closing bracket, check whether it matches the top of the stack. If not, or if the stack is empty, return False immediately. After the full scan, return True only if the stack is empty: any remaining openers mean unclosed brackets.

I’ll use a hash map from closing to opening bracket to keep the matching logic clean. Three failure modes to handle: wrong bracket type, a closing bracket with no opener on the stack, and opening brackets still on the stack at the end.

This is O(n) time and O(n) space. Let me code it up.”

---

Example Interview Dialogue

Interviewer: Given a string of brackets, determine if it’s valid.

Candidate: Just to confirm: the string contains only bracket characters, and I return a boolean?

Interviewer: Correct.

Candidate: The key property of valid bracket strings is that they close in reverse order, LIFO. That’s a stack. I push opening brackets and pop against closing ones. Three ways it can be invalid: a closer with the wrong type on top of the stack, a closer with an empty stack, or leftover openers when I’m done.

Interviewer: What data structure do you use to map closing brackets to their expected openers?

Candidate: A dictionary: {')': '(', ']': '[', '}': '{'}. When I encounter a closing bracket, I look up its expected opener and compare to stack[-1]. It’s cleaner than a chain of if/elif conditions and easy to extend.

Interviewer: What’s the space complexity, and can you do better?

Candidate: O(n) in the worst case, a string of all opening brackets fills the stack completely. For the general case with three bracket types, I don’t think we can do better. But if the input only used one bracket type, I could replace the stack with a counter that increments on ( and decrements on ), returning False if it goes negative or ends non-zero. That’s O(1) space but only works for a single bracket type.

Interviewer: How would you find the minimum number of bracket removals to make a string valid?

Candidate: That’s LeetCode #1249. I’d use a stack to track unmatched openers by index, and a set to track unmatched closers. After scanning, any index still in the stack or set represents a character that must be removed. The answer is the total count of such characters.

---

Related Problems

Valid Parentheses is the entry point for a rich family of stack-based bracket problems:

• Minimum Remove to Make Valid Parentheses (LeetCode #1249). Track indices of unmatched brackets and remove them. Extends the stack with index tracking.
• Generate Parentheses (LeetCode #22). Use backtracking to generate all valid combinations. Tests bracket generation vs. validation.
• Longest Valid Parentheses (LeetCode #32). Find the longest valid substring. Extends the stack approach with length tracking.
• Score of Parentheses (LeetCode #856). Compute a score based on nesting depth. Uses a stack to track depth and accumulate scores.
• Minimum Add to Make Parentheses Valid (LeetCode #921). Count minimum insertions needed. Uses a counter-based approach without full stack.

The jump from Valid Parentheses to Minimum Remove (#1249) is the most common interview escalation.

---

Practice This in a Mock Interview

The logic feels obvious in a walkthrough: the stack is a natural fit, the failure modes are clear, the final empty-stack check is easy to remember. But the problem has a well-documented failure mode in interviews: candidates who rush through it (since it’s rated Easy) skip the final len(stack) == 0 check, forget to guard against an empty stack before popping, or fail to articulate the three failure modes when probed.

Speed without precision is the enemy on Easy problems. An interviewer watching you handle a warm-up question quickly but sloppily will be concerned, not impressed. The goal is fluency: fast and complete, with clear verbal reasoning throughout.

Start a mock interview for Valid Parentheses on Intervu.

---

Related Problems to Practice

• Min Stack — Stack design with O(1) min retrieval.
• Evaluate Reverse Polish Notation — Stack-based expression evaluation.
• Basic Calculator — Stack-based parsing with nested parentheses.

Further reading:

• How to Prepare for a Coding Interview in 2026, the complete roadmap and study plans
• Why LeetCode alone isn’t enough, and what to practice instead
• Practice any LeetCode problem as a live mock interview
• The Grind 75 Pathway, a structured study plan with AI practice links
• Browse all walkthroughs on GitHub, condensed solutions with code