20 - Valid Parentheses

Difficulty: Easy | Pattern: Stack | Company tags: Google, Amazon, Facebook, Microsoft

Problem Statement

Given a string s containing just the characters '(', ')', '{', '}', '[', ']', 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.

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

Constraints: 1 <= s.length <= 10^4; s consists of parentheses only: '()[]{}'

Approach: Stack

Key insight: Use a stack. Push every opening bracket onto the stack. When you see a closing bracket, check if it matches the top of the stack. If it does, pop the top. If it doesn't match, or the stack is empty when you need to pop, the string is invalid. At the end, the stack must be empty.

Why a stack? The Last-In-First-Out (LIFO) property exactly models the nesting requirement: the most recently opened bracket must be closed first.

Algorithm:

1. Create a mapping from each closing bracket to its matching opening bracket
2. For each character in s:
   • If it's an opening bracket ((, {, [): push onto stack
   • If it's a closing bracket: check if stack is empty OR top ≠ corresponding open bracket → return False; otherwise pop
3. Return len(stack) == 0 (all openers were matched)

Algorithm Flow

Solution (Python)

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

Dry Run

Input: s = "({[]})", expected: True

Step	Char	Stack	Action
1	(	[(]	Push
2	{	[(, {]	Push
3	[	[(, {, []	Push
4	]	[(, {]	Pop [ (matches)
5	}	[(]	Pop { (matches)
6	)	[]	Pop ( (matches)
End	—	[]	Stack empty → True

Input: s = "([)]", expected: False

Step	Char	Stack	Action
1	(	[(]	Push
2	[	[(, []	Push
3	)	mismatch!	top is [, need ( → return False

Edge Cases

• Empty string "" → valid (empty stack at end)
• Single character "(" → invalid (stack has unclosed bracket)
• All openers "(((" → invalid (stack not empty)
• All closers ")))" → invalid (stack empty when trying to pop)
• Odd-length string → always invalid (can return early with length check)

Optimization: Add if len(s) % 2 != 0: return False at the start (odd-length strings can't be valid).

Complexity

• Time: O(n) — one pass through the string
• Space: O(n) — worst case, all characters are opening brackets pushed to stack

Key Terms

Term	Definition (in context of this problem)
Stack (LIFO)	Models the nesting requirement — the most recently opened bracket is the first one that must be closed.
Matching map	A dict from each closing bracket to its corresponding opening bracket, used for O(1) lookup during validation.
Balanced string	A string where every opener has exactly one matching closer in the correct nested order, and the stack ends empty.
Early termination	Returning False as soon as a mismatch or empty-stack pop is detected, avoiding unnecessary further scanning.

FAQ

1. Can this be solved without extra space? Not in general — a stack (or equivalent counting structure) is required because bracket order matters, not just counts. For a single bracket type only, you could use a counter instead of a stack, but with multiple bracket types you need to know which type is currently open, requiring O(n) space in the worst case.
2. What if the input string is empty? Return True — an empty string has no unmatched brackets, and the stack remains empty throughout, satisfying the final check.
3. What if the string length is odd? It can never be valid, since every valid string must have pairs of brackets; you can short-circuit with if len(s) % 2 != 0: return False before the main loop as an optimization.
4. What's the common follow-up interviewers ask? "Return the minimum number of insertions to make the string valid" (LeetCode 921/1249) or "generate all valid combinations of n pairs of parentheses" (LeetCode 22, backtracking), both building on the same stack-based validity concept.
5. How would this change if brackets could also appear alongside other characters (e.g., letters)? Simply skip/ignore non-bracket characters in the loop — push/pop logic only triggers on recognized bracket characters, and everything else passes through unaffected.

Quick Revision

• Use a stack to track currently open, unmatched brackets.
• On an opening bracket, push it; on a closing bracket, check the top of the stack for a match.
• If the stack is empty or the top doesn't match the required opener, the string is invalid immediately.
• At the end, the string is valid only if the stack is completely empty (no unclosed openers remain).
• Odd-length strings can never be valid — useful as an early exit optimization.
• Time complexity: O(n), single pass over the string.
• Space complexity: O(n) worst case (e.g., all openers, like "(((").
• Classic pitfall: checking bracket type equality without checking if the stack is empty first, causing an index error on pop.

Related Problems

• 32-LongestValidParentheses — extends this exact stack technique to find the longest valid substring.
• LeetCode 921 (Minimum Add to Make Parentheses Valid) and LeetCode 1249 (Minimum Remove to Make Valid Parentheses) — same stack/counting pattern for bracket validity; not in this directory.
• LeetCode 22 (Generate Parentheses) — related bracket-matching pattern solved via backtracking instead of a stack.