FresherFresher (0–1 yrs)CodingPythonAmazonMetaMicrosoft

Valid Parentheses

Given a string of ()[]{} only, return whether every open bracket is closed by the same type in the correct order.

Answers use simple, clear English.

Time: O(n)Space: O(n)

Quick interview answer

Use a stack: push openings; on a close, pop and verify the match. Closing on empty stack is invalid. End with an empty stack.

Detailed answer

Use a stack: push openings; on a close, pop and verify the match. Closing on empty stack is invalid. End with an empty stack. Same stack discipline validates nested markup and expression parsers.

Full explanation

Same stack discipline validates nested markup and expression parsers.

Real example & use case

IDE live bracket matching highlights the partner of the cursor brace.

Pros & cons

Pros: clear O(n) invariant. Cons: O(n) stack for deeply nested input.

Code example

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

Practice code · python (view only · no execution)

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

#stack#string