Valid Parentheses – Solution & Complexity

Q: What is the time and space complexity of Valid Parentheses?

The optimal Valid Parentheses solution runs in `O(n)` time and `O(n)` space. Push opening brackets onto a stack and pop to match each closing bracket.

Q: What is the most efficient way to solve Valid Parentheses?

Push opening brackets onto a stack and pop to match each closing bracket. This gives `O(n)` time complexity, and is a classic strings and stack problem.

Q: How do you solve Valid Parentheses in Python & JavaScript?

We provide a worked Valid Parentheses solution in Python & JavaScript with a step-by-step explanation above. You can also open the interactive editor to write and run your own Python solution against the test cases in the browser.

Q: Is Valid Parentheses an easy or hard interview question?

Valid Parentheses is generally rated **Easy**. It tests strings and stack, which are common coding-interview patterns.

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. 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. 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. 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. 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

Valid Parentheses – Solution & Complexity

1. Understand Valid Nesting

2. Why Counting Is Not Enough

3. Use a Stack for Open Brackets

4. Handle Closing Brackets

5. Complete Solution and Complexity

FAQ

What is the time and space complexity of Valid Parentheses?

What is the most efficient way to solve Valid Parentheses?

How do you solve Valid Parentheses in Python & JavaScript?

Is Valid Parentheses an easy or hard interview question?