Valid Parentheses

Counting brackets tells you how many openings and closings exist. A stack tells you whether they close in the only order that nesting allows.

The contract and the answer direction

The input is a string containing only (, ), [, ], {, and }. Its length is between 1 and 10^4. Return a boolean:

• True if every opening bracket has the same type of closing bracket.
• True only if brackets close in last-opened-first-closed order.
• False if a closing bracket has no matching opening bracket or if any opening bracket remains unmatched.

The Valid Parentheses solution is a left-to-right scan with a stack:

1. Push every opening bracket.
2. For each closing bracket, check the stack's top element.
3. The top must be the matching opening bracket.
4. Pop the match.
5. Accept only if the stack is empty after the scan.

The stack is not just a generic container here. Its entries represent unresolved opening obligations: brackets that have been seen but not closed yet.

Why counting brackets fails

A first attempt might count opening and closing brackets. If the totals match, perhaps the string is balanced.

That handles only one condition: quantity. It does not handle nesting or bracket type.

Consider:

([)]

There are two opening brackets and two closing brackets. The counts balance. But the sequence fails:

1. ( creates an unresolved obligation.
2. [ creates a newer obligation.
3. ) arrives and tries to close (.
4. [ is still the newest unresolved opening bracket, so ) is illegal.

The problem is structural. The newest opening bracket must be closed first. This is last in, first out, or LIFO.

A queue would close the oldest opening bracket first. That is FIFO behavior, the opposite of what nesting requires. A balanced brackets stack works because it preserves exactly one piece of information that counting throws away: the order of unresolved openings.

The repeated work in a brute-force approach is searching backward through earlier characters to find a possible match while also checking whether inner brackets were handled correctly. The stack records that needed history once, as we scan. No repeated search is necessary.

Name the state and derive the invariant

Use a mapping from each closing bracket to the opening bracket it requires:

{
    ")": "(",
    "]": "[",
    "}": "{",
}

This makes the matching rule explicit instead of scattering several conditionals through the loop.

The key invariant is:

After processing any prefix that has not failed, the stack contains exactly the unmatched opening brackets from that prefix, in their opening order. The newest unresolved opening bracket is at the top.

This one sentence derives every operation.

When the character is an opener

An opening bracket creates a new obligation. It must be closed later, so push it:

stack.append(opener)

When the character is a closer

A closer has one legal target: the newest unresolved opener.

There are two immediate failure cases:

• The stack is empty. This is a premature closer.
• The stack's top does not match the required opener. This is a type or nesting mismatch.

Only after checking the top should you pop it. The pop discharges the obligation.

Why leftovers matter

Suppose the scan never encounters an illegal closer:

(())

Every closer found a valid top element. The stack ends empty, so the string is valid.

Now consider:

(()

The final ) correctly closes the inner (, but the outer ( remains on the stack. A successful scan is not enough. Every obligation must be discharged, so the final stack must be empty.

Trace the stack through valid and invalid inputs

A detailed trace makes the state visible. For the valid string ({[]}):

The stack behaves like a pile of unfinished rooms. You must finish the innermost room before you can leave the outer one.

Now inspect common failures.

Wrong type at the top

[(])

The state changes like this:

] requires [, but ( is on top. It is not enough to find [ somewhere below the top. The inner obligation must be resolved first.

Premature closer

)(

The first character is ), but the stack is empty. There is no earlier opening bracket to match it. Return False immediately.

Leftover opener

(() 

The final stack contains (. That remaining entry is direct evidence of an unmatched opening bracket, so return False.

Adjacent pairs

()[]{}

This is valid even though the brackets are not nested. Each closer matches the only current obligation, and the stack repeatedly returns to empty.

Empty behavior

Under the balanced-sequence rule, an empty string would leave the stack empty and therefore be conceptually valid. However, this problem's authoritative constraint requires the input length to be at least 1, so the implementation does not need a special empty-input branch. The final emptiness check already gives the natural behavior.

Prove the algorithm is correct

An interview explanation should do more than narrate the code. State why the state remains trustworthy.

Initialization

Before scanning any characters, there are no unresolved opening brackets. The stack is empty, so the invariant holds.

Maintenance

Assume the invariant holds before processing the next character.

• If the character is an opening bracket, pushing it adds exactly the new unresolved obligation. The stack still contains all and only the unmatched openers, in order.
• If the character is a closing bracket and the stack is empty, there is no possible matching opener. The string is invalid.
• If the character is a closing bracket and the top does not match, the newest unresolved obligation cannot be closed by this bracket. The string is invalid.
• If the character matches the top, popping removes exactly the obligation that this closer discharges. The invariant is preserved.

Therefore, every scan that has not returned False preserves the invariant.

Termination

At the end:

• An empty stack means every opening bracket was matched and popped.
• A nonempty stack means at least one opening obligation remains.

So returning True exactly when the stack is empty satisfies all three validity conditions: matching types, correct order, and complete pairing.

Implement the Python solution

Here is the complete Valid Parentheses Python implementation:

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

    # Each closing bracket names the opening bracket it must match.
    matching_open = {
        ")": "(",
        "]": "[",
        "}": "{",
    }

    for char in s:
        if char in matching_open:
            # A closer needs a matching unresolved opener on top.
            if not stack or stack[-1] != matching_open[char]:
                return False

            stack.pop()
        else:
            # Under the input contract, this is an opening bracket.
            stack.append(char)

    # No opening obligations may remain.
    return not stack

The mapping serves two purposes:

• Membership in matching_open identifies closing brackets.
• The mapped value identifies the exact opener required at the top.

The input contract guarantees that every character is one of the six bracket characters. That is why the else branch can treat the character as an opener without adding a separate validation branch. Do not silently broaden this function to accept arbitrary text or whitespace; that would change the problem's contract.

One implementation detail deserves attention: validate before popping.

This is safe:

if not stack or stack[-1] != matching_open[char]:
    return False

stack.pop()

This is harder to reason about:

top = stack.pop()
if top != matching_open[char]:
    return False

The second version can still return the correct boolean, but it mutates the state before confirming that the closer is legal. In a larger parser, that makes debugging and recovery more difficult. Keep the state unchanged until the transition has been validated.

Complexity and interview edge checks

Let n be the string length.

• Time: O(n). Each character is inspected once. Stack operations and dictionary lookups take constant time.
• Auxiliary space: O(n) in the worst case. A string made entirely of opening brackets stores all of them.

Before submitting, test the failure boundaries rather than only the happy path:

The usual bugs are predictable:

• Popping before checking the top.
• Forgetting the empty-stack guard for a premature closer.
• Checking whether a matching opener exists anywhere in the stack instead of checking only the top.
• Returning True after the scan without checking for leftover openers.
• Reversing the mapping so that opening brackets, rather than closing brackets, are the lookup keys.

The durable interview rule is simple:

When processing creates unresolved obligations, and those obligations must be resolved in reverse creation order, use a stack. Define exactly what each stack entry means, validate the newest obligation before removing it, and inspect the final state for leftovers.

That is the transferable skill behind this problem. You are not memorizing a bracket function. You are recognizing nesting, turning it into LIFO state, and letting the invariant drive the implementation.