How to Explain Valid Parentheses in a Coding Interview (Step-by-Step)

Valid Parentheses is a classic stack problem — but “use a stack” is only half the answer. The part that separates clean responses from rushed ones is articulating exactly what goes on the stack, when to pop, and the five failure conditions you need to cover.

In this post, you’ll learn how to walk an interviewer through LeetCode 20 with precision: the bracket-mapping design decision, the push/pop logic, a full character-by-character stack trace, and every edge case that catches candidates off guard.

Problem Statement

Examples

Constraints

• 1 <= s.length <= 104
• s consists of parentheses only: '()[]{}'

What Is the Problem?

“I’m given a string of bracket characters. I need to verify that every opening bracket is eventually closed by the correct matching bracket, and that they’re properly nested — meaning the most recently opened bracket must be the first one closed. That last-in-first-out ordering is the exact behaviour of a stack.”

Naming the LIFO property and connecting it directly to a stack is the kind of reasoning that shows an interviewer you understand why a data structure fits — not just that it does.

The Key Insight — LIFO Matches Nesting

“The string '([)]' illustrates why order matters. Both bracket types appear in equal numbers, so a simple counter would incorrectly pass it. Only a stack correctly rejects it — when ')' arrives, the top of the stack is '[', not '(', so we return false.”

The Bracket Mapping Design Decision

Before writing a single line of logic, decide how to encode the bracket relationships. The cleanest approach is a HashMap mapping each closing bracket to its expected opening bracket:

“Mapping closing to opening (rather than the reverse) means the check on every closing bracket is a single lookup: ‘does the top of the stack equal mapping[char]?’ — one line, no branching, easy to extend to new bracket types.”

Step 2: Explain the Algorithm in Plain English

Stack Trace Visualised — s = “{[()]}”

Tracing every character. The stack grows upward — the top is the most recently pushed element.

Contrast — Invalid String “([)]”

Here’s where the stack catches an error a counter-based approach would miss:

Step 3: Talk Through the Code

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

        for char in s:
            if char in mapping:
                # Closing bracket: stack must be non-empty and top must match
                top = stack.pop() if stack else '#'   # '#' sentinel for empty stack
                if mapping[char] != top:
                    return False
            else:
                # Opening bracket: push onto stack
                stack.append(char)

        # Valid only if every opener was matched and popped
        return not stack

Point out the '#' sentinel — when the stack is empty and a closing bracket arrives, we need something to compare against that will never equal a valid opener. Using '#' (or any non-bracket character) avoids a separate if stack branch and keeps the comparison logic in one place.

Step 4: Highlight Edge Cases

Step 5: State Time and Space Complexity

“Time is O(n) — one pass, one push or pop per character, all O(1) operations. Space is O(n) in the worst case: a string of only opening brackets pushes every character onto the stack. In the best case — alternating open/close pairs — the stack never holds more than one element.”

Interview Checklist for Valid Parentheses

• Restate — “each opener must be closed by the same bracket type, in correct nesting order”
• Name the LIFO property and explain why it maps directly to a stack
• Explain the mapping design decision — close bracket maps to its expected open bracket
• Describe the push/pop logic: openers push, closers check-and-pop
• Explain the empty-stack guard — sentinel '#' or explicit if not stack check
• Return not stack at the end — non-empty means unclosed openers remain
• Call out “([)]” — why a counter fails but a stack catches it
• Call out odd-length early exit as a bonus optimisation
• Call out unclosed openers — stack non-empty at the end
• State O(n) time and O(n) space — mention the best-case O(1) space scenario

Related Problems to Practice

If you can solve Valid Parentheses cleanly, try these next: