LeetCode 20 - Valid Parentheses

It has been a while since I last returned to an Easy problem. I have had plenty of other material to organize, but I still wanted to keep the problem-solving rhythm going.

This problem asks whether a string containing only parentheses, brackets, and braces closes every opening symbol with the correct type and order. Because the most recently opened bracket must be closed first, I used a stack.

Problem link and explanation

Problem link: 20. Valid Parentheses
Summary: Return true when every opening bracket is closed by the matching bracket in the correct order.

Matching counts are not enough. ([)] contains the same number of opening and closing symbols, but it violates the rule that the most recently opened bracket must be matched and closed first.

"()"      -> true
"()[]{}"  -> true
"(]"      -> false
"([)]"    -> false
"{[]}"    -> true

When the scan finds an opening bracket, it has to remember that bracket until a matching closer appears. When it finds a closing bracket, it only needs to compare it with the most recent unmatched opener.

Approach

I scan the string from left to right and push every opening bracket onto the stack. For a closing bracket, I compare it with the top of the stack. If they form a pair, I pop the opener. Any mismatch makes the string invalid immediately.

if ch == '(' or ch == '{' or ch == '[':
    stack.append(ch)
elif stack and self.is_pair(stack[-1], ch):
    stack.pop()
else:
    return False

A stack follows last-in, first-out order. After reading ([, the [ was opened after (, so ] must appear first. Checking only the stack’s top preserves that nesting rule without searching through all unmatched brackets.

I separated the three valid combinations into an is_pair helper.

def is_pair(self, open_bracket, close_bracket):
    return (
        (open_bracket == '(' and close_bracket == ')')
        or (open_bracket == '{' and close_bracket == '}')
        or (open_bracket == '[' and close_bracket == ']')
    )

Finishing the loop without a mismatch is still not sufficient. A string such as (( leaves unmatched opening brackets in the stack. The final result must therefore check that the stack is empty.

Troubleshooting

Reading the top element before checking whether the stack contains anything would fail on input such as ")". The condition checks the stack first and only evaluates the pair comparison when an opener exists.

elif stack and self.is_pair(stack[-1], ch):

Python stops evaluating an and expression as soon as its left side is false. If the stack is empty, it never evaluates stack[-1] and falls through to the false result.

The comparison also has to use the most recent opener rather than merely checking whether a matching opener exists somewhere in the stack. For ([)], the first closing parenthesis encounters [ at the top. Those symbols do not form a pair, so the function correctly rejects the string at that point.

Complexity analysis

Let n be the length of the input string.

Time complexity: O(n)
- The algorithm processes each character once. Stack append, pop, and top access are constant-time operations.
Space complexity: O(n)
- In the worst case, every character is an opening bracket, so the stack stores all n characters.

Implementation code

class Solution:
    def is_pair(self, open_bracket, close_bracket):
        return (
            (open_bracket == '(' and close_bracket == ')')
            or (open_bracket == '{' and close_bracket == '}')
            or (open_bracket == '[' and close_bracket == ']')
        )

    def isValid(self, s: str) -> bool:
        stack = []

        for ch in s:
            if ch == '(' or ch == '{' or ch == '[':
                stack.append(ch)
            elif stack and self.is_pair(stack[-1], ch):
                stack.pop()
            else:
                return False

        return not stack

Summary and reflection

There are two conditions to check: whether every closer matches the latest opener, and whether the stack is empty after the loop. Even an Easy problem can make my hands pause when I return to it after some time away, so repetition still matters. The point is not to memorize the code, but to reinforce the reason each condition is necessary.