Valid Parentheses

Determine if the input string has valid bracket pairs.

Pattern

Stack Matching

This problem follows the Stack Matching pattern, commonly found in the Stack category. Recognizing this pattern is key to solving it efficiently in an interview setting.

Approach

How to Solve It

Push opening brackets. Pop on closing bracket and check if they match.

Key Insight

A stack naturally handles nesting — the most recent opening bracket must match the next closing bracket, which is exactly LIFO order.

Step-by-step

1Create an empty stack
2For each character in the string:
3If it's an opening bracket, push it onto the stack
4If it's a closing bracket, check if the stack top matches
5If the stack is empty at the end, the string is valid

Pseudocode

stack = []
pairs = {')': '(', ']': '[', '}': '{'}
for char in s:
    if char in pairs:
        if not stack or stack[-1] != pairs[char]:
            return false
        stack.pop()
    else:
        stack.push(char)
return len(stack) == 0

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(n)

Master this pattern with YeetCode

Practice Valid Parentheses and similar Stack problems with flashcards. Build pattern recognition through active recall.

Practice this problem

NextMin Stack →