Valid Parentheses

Medium · rating 1150 · stack, strings

Read a line containing only the characters ()[]{}. Print YES if every bracket is closed by the same type in the correct order, otherwise NO.

Editorial

Approach

Bracket matching is the canonical use case for a stack. Scan left to right: push every opening bracket. On a closing bracket, the most recently opened bracket must be its match — so pop the stack and compare. If it doesn't match (or the stack is empty), the string is invalid.

Key insight

Valid nesting is last-opened, first-closed — exactly LIFO order, which is what a stack models. At the end, a valid string leaves the stack empty; anything left over means an unclosed bracket.

pairs = {')':'(', ']':'[', '}':'{'}
stack = []
for c in s:
    if c in '([{': stack.append(c)
    elif not stack or stack.pop() != pairs[c]:
        return False
return not stack

Complexity

Time: O(n). Space: O(n) in the worst case (all opening brackets).

Open Valid Parentheses in Code Arena →