Valid Parentheses: The Stack Problem Every Interview Starts With

Valid Parentheses is LeetCode 20, rated Easy, and it is asked constantly because it tests one idea cleanly: the most recently opened bracket must be the first one closed. That is last-in, first-out. That is a stack. If you reach for a counter, you will pass () and fail ([)], and the interviewer will ask you why.

The problem

Given a string containing only (, ), {, }, [, and ], return whether it is valid. Valid means every opening bracket is closed by the same type, in the correct order, and every closing bracket has a matching open one before it. ()[]{} is valid. ([)] is not. (] is not. ] is not.

The solution

Push openers. On a closer, the top of the stack must be its matching opener. At the end, the stack must be empty.

def isValid(s: str) -> bool:
    pairs = {")": "(", "]": "[", "}": "{"}
    stack: list[str] = []
    for ch in s:
        if ch in pairs:
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()
        else:
            stack.append(ch)
    return not stack

Time is O(n): one pass, constant work per character. Space is O(n) in the worst case, a string of all openers.

Two details separate a clean answer from a fumbled one. The dictionary is keyed by the closer, so the lookup happens on the character you are trying to match, and you never write six if branches. And the return is not stack, not True. Returning True after the loop passes (() and fails the test.

The three edge cases they will try

Input	Why it matters	What the code does
""	Empty string is valid	Loop does not run, stack is empty, returns True
"]"	A closer with nothing to match	not stack is true on the first character, returns False
"(("	Openers that never close	Loop finishes, stack has two items, returns False

The second case is the one that crashes a solution that does stack.pop() before checking emptiness. Say the check out loud when you write it.

Why a counter fails

A single depth counter — increment on open, decrement on close, fail if it goes negative — is correct for one bracket type. With three types it loses the information about which bracket is open. ([)] keeps the counter non-negative the whole way and ends at zero. The stack rejects it when ) meets [ on top. If the interviewer asks "can you do it in O(1) space," the answer is no for mixed bracket types, and the reason is exactly this.

Follow-ups that turn it into a design question

Minimum removals to make it valid. Track the indices of unmatched openers on the stack and the count of unmatched closers. Remove both sets. This is LeetCode 1249 for parentheses only, and the stack is the same.

Longest valid substring. Push indices instead of characters, seed the stack with -1, and on each closer compute i - stack[-1] after popping. The stack now stores boundaries, which is the step from "is it valid" to "how much of it is valid."

Streaming input. The algorithm is already streaming; it consumes one character at a time and never looks back. If the input is too large to hold, the stack is still bounded by the maximum nesting depth, not by the input length. That is the observation to make if they ask about a file that does not fit in memory.

Generalizing to tags. An HTML or XML validator is the same loop with multi-character tokens. Tokenize first, then run the stack on tag names. The structure of the answer does not change; the tokenizer does.

The reason this problem persists is that the stack is the only correct structure, and most people know that before they sit down. What the interviewer is watching is whether you check for an empty stack before you pop, whether you return not stack, and whether you can explain in one sentence why a counter is not enough.