Valid Parentheses

Problem

Given a string s containing just the characters (){}[], determine if the input string is valid. The brackets must close in the correct order — every opening bracket has a matching closing bracket of the same type, and open brackets must be closed in the reverse order they were opened.

Examples: "()" → true, "(]" → false,"{[]}" → true.

What the interviewer is testing

• Do you recognize this as the canonical "when do I use a stack" problem?
• Do you handle the edge cases (empty string, single closing bracket, unmatched openers)?
• Do you use a clean pairing map instead of six ugly branches?

Why a stack

Brackets close in reverse order. Reverse order = LIFO = stack. Push every opener, and every closer must match the top of the stack. If it doesn't, the string is invalid. At the end, the stack must be empty.

Optimal solution — O(n) time, O(n) space

def is_valid(s: str) -> bool:
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in pairs:                        # closer
            if not stack or stack.pop() != pairs[ch]:
                return False
        else:                                  # opener
            stack.append(ch)
    return not stack

Two things people mess up: (a) forgetting the empty-stack check on a closer, which throws on ")"; (b) forgetting the finalnot stack check, which returns true for "(".

Complexity — what to say out loud

"Time O(n) — one pass. Space O(n) in the worst case where the input is all openers."

Edge cases the interviewer will ask about

• Empty string — valid. Our code returns not stack = true.
• Single closer — ")" — our first line catches empty stack, returns false.
• Only openers — "(((" — the stack is non-empty at the end, we return false.
• Non-bracket characters mixed in — clarify with the interviewer whether the input can contain other characters; if yes, skip them.

Common follow-ups

• "How would you check balanced HTML tags?" — Same idea; the stack holds tag names, and each closing tag must match the top.
• "What if you only need to know how many characters to add to make it valid?" — Two counters: unmatched openers and unmatched closers. Answer is their sum.
• "What if the stack is too big?" — With just ( and ), replace the stack with a single counter. Still O(n) time, now O(1) space.

How to verbalize your answer

"Brackets close in reverse order, which is exactly what a stack is for. I'll push each opener and match each closer against the top. If they don't match, or the stack is empty when I see a closer, return false. At the end, the stack must be empty. Time O(n), space O(n)."

The interviewer wants to hear "stack" in the first sentence. Say it.