LeetEye LeetEye
Medium Stack ~5 min

Valid Parentheses

stack valid-parentheses

Problem

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:
1. Open brackets must be closed by the same type of brackets
2. Open brackets must be closed in the correct order
3. Every close bracket has a corresponding open bracket of the same type

Examples

Example 1
Input: s = "()"
Output: true
Example 2
Input: s = "()[]{}"
Output: true
Example 3
Input: s = "(]"
Output: false
Example 4
Input: s = "([)]"
Output: false
Example 5
Input: s = "{[]}"
Output: true
Key Insight

Last opened bracket must be first to close.

Nested structures = stack. Push openers, pop and match on closers, end with empty stack.

How to Approach This Problem

Pattern Recognition: When you see keywords like valid parentheses stack, think Stack.

Step-by-Step Reasoning

1 The key property that makes a stack appropriate is:
Answer: The most recent open bracket must close first
LIFO behavior. The innermost (most recently opened) bracket must be matched first.
2 When you see an opening bracket '(', '[', or '{', you should:
Answer: Push the closing bracket onto the stack
Empty stack means no opener to match = invalid. Otherwise, top of stack should be the matching opener.
3 After processing all characters, the string is valid if:
Answer: Both A and B
We need no mismatches during processing AND no unmatched openers left.
4 "([)]" fails because:
Answer: The '[' must close before ')' but ')' comes first
After ([, stack is [(, []. Seeing ) requires ( on top, but [ is on top. Nesting violation.

Solution

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

Complexity Analysis

Time O(n)
Space O(n)

Master This Pattern

Build intuition with interactive MCQs. Practice Stack problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye