The Core Idea

This is a classic stack problem. We scan the string left to right, pushing every opening parenthesis onto a stack, and popping when we see a closing one. If the stack is empty at the end, everything matched up perfectly. Let's walk through the reasoning carefully so the approach feels inevitable, not memorized.

Thinking Through Examples

Before writing any code, let's build intuition from a few cases:

(()): valid. Each open has a matching close in the right order.
)(: invalid. We see a close before any open. The order is wrong.
()(): valid. Two independent pairs.
((): invalid. One open was never closed.
abc(def)ghi: valid. Non-parenthesis characters should be ignored.

The key insight is that "correct order" means a closing paren must always correspond to the most recently opened unmatched paren. That last-in, first-out behavior is exactly what a stack gives us.

The Stack Approach

The algorithm has three simple rules:

See a (: push it onto the stack.
See a ): if the stack is empty, we have an unmatched close, return False. Otherwise, pop from the stack.
End of string: if the stack is empty, all opens were matched. If not, some open was never closed, return False.

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

    for char in s:
        if char == '(':
            stack.append(char)
        elif char == ')':
            if not stack:
                return False  # Unmatched closing paren
            stack.pop()

    return len(stack) == 0  # True only if all opens were matched

Notice we don't even need to store the actual character in the stack since there's only one type of bracket here. We're really just counting depth, but using a stack makes the intent clear and generalizes naturally (more on that in a moment).

Tracing Through an Example

Let's trace s = "(())" step by step:

Char (: push. Stack: ['(']
Char (: push. Stack: ['(', '(']
Char ): pop. Stack: ['(']
Char ): pop. Stack: []
End: stack is empty, return True.

Now trace s = ")(":

Char ): stack is empty, return False immediately.

The early return is important. We don't need to finish scanning once we've detected a violation.

Complexity

Both time and space complexity are straightforward here:

Time: $O(n)$ where $n$ is the length of the string. We visit each character exactly once.
Space: $O(n)$ in the worst case. A string like (((((( would push every character onto the stack before we realize nothing closes.

If space is a concern, we can replace the stack with a simple counter since we only have one bracket type. Increment on (, decrement on ), and return False if the counter ever goes negative.

def is_balanced_counter(s: str) -> bool:
    depth = 0

    for char in s:
        if char == '(':
            depth += 1
        elif char == ')':
            depth -= 1
            if depth < 0:
                return False  # More closes than opens so far

    return depth == 0

This runs in $O(1)$ space. But the stack version is worth knowing because it extends naturally to the harder problem.

The Natural Extension: Multiple Bracket Types

Interviewers often follow up with: "What if we also have [] and {}?" The counter approach breaks down immediately. The stack approach handles it cleanly. We push any open bracket, and when we see a close, we check that the top of the stack is the matching open type.

def is_balanced_multi(s: str) -> bool:
    stack = []
    matching = {')': '(', ']': '[', '}': '{'}

    for char in s:
        if char in '([{':
            stack.append(char)
        elif char in ')]}':
            if not stack or stack[-1] != matching[char]:
                return False
            stack.pop()

    return len(stack) == 0

This handles cases like ([)] being invalid (interleaved brackets) while ([{}]) is valid. The core logic is identical, the dictionary just tells us what counts as a match.

Edge Cases Worth Mentioning

Empty string: returns True. An empty string has no unmatched parens. The loop never runs, the stack stays empty.
No parens at all: "hello" returns True for the same reason. This matches the spec since every open (zero of them) has a matching close.
Only closes: ")))" returns False on the very first character.
Only opens: "(((" falls through to len(stack) == 0 which is False.

2071. Balanced Parentheses Detection

Similar Questions