Valid Parentheses

Signal

"Every opener must be closed by its matching type, most-recently-opened first" is last-in-first-out by definition — any nesting/matching problem over a linear sequence is a stack, full stop.

Approach

Walk the string once. Push every opening bracket. On a closing bracket, pop and check the popped opener matches the expected type — if the stack is empty or the types don't match, it's invalid immediately. At the end, the stack must be empty (no unclosed openers left).

Skeleton

stack = []
pairs = {')': '(', ']': '[', '}': '{'}
for c in s:
    if c in pairs.values(): stack.push(c)
    else:
        if stack empty or stack.pop() != pairs[c]: return False
return stack is empty

Solution

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

Complexity

O(n) time — one pass, O(1) work per character. O(n) space for the stack in the worst case (all openers).

Pitfalls

• Forgetting the empty-stack check before popping on a closing bracket — ")" alone would otherwise crash instead of returning False.
• Forgetting the final "stack must be empty" check — "(((" passes every per-character check but leaves unclosed openers.
• Mapping closer→opener (as above) is cleaner than opener→closer; trying to look ahead for the matching closer is unnecessary complexity.