Valid Parentheses (LC 20)

Problem Statement

Given a string s containing only the characters (, ), {, }, [, ], determine if the brackets are validly nested. A string is valid if:

• Every open bracket is closed by the same type of bracket.
• Open brackets are closed in the correct order.
• Every close bracket has a matching open bracket.

Example 1:

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

Example 2:

Input:  s = "([)]"
Output: false

Example 3:

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

Constraints:

• 1 <= s.length <= 10^4
• s contains only the six bracket characters.

Difficulty: Easy

---

Pattern Recognition

• Input structure: string of brackets.
• What are we checking? matching pairs with LIFO (last-in-first-out) order.
• Pattern: stack.
• Why: whenever you see a close bracket, it must match the most recent unmatched open bracket. That is exactly LIFO semantics.

---

Approach

Brute Force — Repeated Replacement

Keep removing "()", "{}", "[]" from s until no changes. If s is empty at the end, it was valid. O(n^2) per replacement cycle; O(n^3) worst case. Passes LeetCode but wasteful and not what interviewers want to see.

Optimal — Stack

Key Insight: Each close bracket must match the top of the stack. Push opens; on a close, pop and check.

for ch in s:
    if ch is open: push onto stack
    else:
        if stack empty or top does not match ch: return false
        pop
return stack is empty

You can precompute match = { ')': '(', ']': '[', '}': '{' } for readability.

Time: O(n). Space: O(n) worst case for the stack.

---

Walkthrough

s = "{[()]}":

i	ch	Action	Stack
0	{	push	[{]
1	[	push	[{, []
2	(	push	[{, [, (]
3	)	top is (, pop	[{, []
4	]	top is [, pop	[{]
5	}	top is {, pop	[]

Stack empty → valid.

Contrast s = "([)]":

i	ch	Action	Stack
0	(	push	[(]
1	[	push	[(, []
2	)	top is [, mismatch	—

Return false immediately.

---

Implementation

TypeScript

function isValid(s: string): boolean {
    const stack: string[] = [];
    const match: Record<string, string> = { ')': '(', ']': '[', '}': '{' };
    for (const ch of s) {
        if (ch === '(' || ch === '[' || ch === '{') {
            stack.push(ch);
        } else {
            if (stack.length === 0 || stack.pop() !== match[ch]) return false;
        }
    }
    return stack.length === 0;
}

C++

bool isValid(string s) {
    stack<char> st;
    unordered_map<char, char> match = {{')', '('}, {']', '['}, {'}', '{'}};
    for (char ch : s) {
        if (ch == '(' || ch == '[' || ch == '{') {
            st.push(ch);
        } else {
            if (st.empty() || st.top() != match[ch]) return false;
            st.pop();
        }
    }
    return st.empty();
}

Watch out:

1. Forgetting the empty-stack check before popping crashes on strings that start with a close bracket.
2. Returning true without verifying the stack is empty misses unclosed opens like "([{".
3. Hard-coding 3 ifs instead of a match map is fine but gets brittle if the interviewer adds angle brackets or custom pairs — a map is future-proof.

---

Complexity Analysis

	Time	Space
Repeated replacement	O(n^2) or worse	O(n)
Stack	O(n)	O(n)

Bottleneck: you must inspect every character once. O(n) time is optimal; the stack is bounded by the number of unclosed opens.

---

Edge Cases

1. Empty string — typically returns true. Constraints here say n >= 1, so moot.
2. Odd length — cannot be balanced; early exit with s.length % 2 === 1 → return false is a nice micro-opt.
3. All opens — stack nonempty at end, return false.
4. All closes — first close hits empty-stack check, return false.
5. Nested correctly but mismatched types — "(]" must return false; the match check catches it.
6. Very long valid input — stack may grow to n/2. Fine in memory but avoid recursion-based variants to skip stack-overflow risk.

---

Related Problems

• LC 32 — Longest Valid Parentheses — Same bracket model, track longest matched span with stack or DP.
• LC 678 — Valid Parenthesis String — Adds * as wildcard; use two counters (min/max possible open) or stack with two types.
• LC 921 — Minimum Add to Make Parentheses Valid — Counting version of the stack pattern; no stack required.
• LC 1249 — Minimum Remove to Make Valid Parentheses — Extends to returning a valid modified string.

---

What Is Expected at Each Level

Junior: Implement the stack solution correctly on first pass, explain LIFO intuition, handle the mismatched-type case.

Mid-level: Code it fluently, discuss the odd-length shortcut, contrast with the counter-based variants that work for single-bracket-type inputs.

Senior (L4 target): Nail the code quickly, then dive into LC 32 / 921 / 1249 follow-ups — Google frequently extends this problem to "minimum edits to make valid" or "longest balanced substring" in loop. Discuss space complexity in the worst case ("((((..." -> full stack) and whether you could solve it without a stack when only one bracket type exists.