{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Valid Parentheses – Solution & Complexity

Interview solutions
/
Valid Parentheses
Quick practice for Valid Parentheses: 3 reasoning beats, no typing

Watch: Valid Parentheses with a stack

Brackets close in the reverse order they open, so keep the openers on a stack. Push every opening bracket; on a closing bracket, pop and check that it matches. Counting brackets fails on strings like "([)]". The string is valid only if every pop matched and the stack ends empty. O(n) time, O(n) space.

Solution Walkthrough

  1. Step 1: Understand Valid Nesting

    • Every opening bracket must be closed by the same bracket type.
    • Brackets must close in the reverse order they were opened.
    • That reverse-order requirement is the key clue to use a stack.

  2. Step 2: Why Counting Is Not Enough

    • Counting open and closed brackets can catch some invalid strings.
    • It fails for inputs like (], where the counts look balanced but the types do not match.
    • We need to remember the exact most recent unmatched opening bracket.

  3. Step 3: Use a Stack for Open Brackets

    • Push opening brackets onto a stack.
    • When a closing bracket appears, it must match the bracket at the top of the stack.
    • If the stack is empty or the type is wrong, the string is invalid immediately.
    def is_valid(s):
    stack = []
    pairs = {")": "(", "}": "{", "]": "["}
    for char in s:
        if char in pairs.values():
            stack.append(char)

  4. Step 4: Handle Closing Brackets

    • Store closing-to-opening bracket pairs in a dictionary.
    • For each closing bracket, pop the stack and compare it with the expected opener.
    • At the end, the stack must be empty for all brackets to be matched.
    if char in pairs:
    if not stack or stack.pop() != pairs[char]:
        return False

  5. Step 5: Complete Solution and Complexity

    • The final algorithm scans the string once and uses the stack to enforce correct order.
    • Time complexity is O(n), where n is the length of the string.
    • Space complexity is O(n) in the worst case when all characters are opening brackets.
    def is_valid(s: str) -> bool:
    stack = []
    pairs = {")": "(", "}": "{", "]": "["}

    for char in s:
        if char in pairs.values():
            stack.append(char)
        elif char in pairs:
            if not stack or stack.pop() != pairs[char]:
                return False

    return len(stack) == 0

FAQ

See also

Practice Valid Parentheses online (run code in the browser)Decode String solution (medium)Longest Valid Parentheses solution (hard)Alien Dictionary solution (hard)Binary Tree Inorder Traversal solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?