roadmap/stack/Valid Parentheses

Valid Parentheses

EasyGoogleAmazonMetaBloombergMicrosoft

Problem

Given a string containing just '(', ')', '{', '}', '[', ']', determine if the input string is valid. Open brackets must be closed by the same type and in the correct order.

Intuition — the key insight

The most recently opened bracket must be the first one closed — that's exactly what a stack does. Push opening brackets; when you see a closing bracket, check if it matches the top of the stack. If the stack is empty at the end, all brackets matched.

Approach

Stack matching

Iterate through each character. If it's an opening bracket, push it. If it's a closing bracket, check: is the stack non-empty AND does the top match this closing bracket? If not, return false. After full iteration, valid only if stack is empty.

Complexity

Time

O(n)

Space

O(n)

Single pass through the string O(n). Stack holds at most n/2 opening brackets in the worst case — O(n) space.

Solution code

Python

def isValid(self, s: str) -> bool:
    stack = []
    matching = {')': '(', '}': '{', ']': '['}
    
    for char in s:
        if char in '({[':
            stack.append(char)
        else:
            # Closing bracket
            if not stack or stack[-1] != matching[char]:
                return False
            stack.pop()
    
    return len(stack) == 0

Edge cases to remember

⚠Empty string: returns true (stack empty at end)

⚠Single character like '(': stack has one element, returns false

⚠Closing bracket with empty stack: must return false immediately

⚠All opening brackets: stack non-empty at end, returns false

Hints

What pattern do you think this problem uses?