Valid Parentheses (LC 20)

Pattern: Stack (LIFO matching)
Difficulty: Easy
Key Concept: The most recently opened bracket must be the first one closed — that is LIFO, so a stack does the matching for free.

Problem Statement

Given a string s containing only '(', ')', '{', '}', '[', ']', determine if the input is valid. Valid means brackets are closed by the same type and in the correct order.

Input: String s, 1 <= s.length <= 10^4
Output: boolean

Examples

Input	Output	Why
()	true	matched pair
()[]{}	true	three independent pairs
(]	false	wrong type
([)]	false	wrong order — ( is not the most recent open when ) arrives
{[]}	true	properly nested
(	false	never closed
)	false	closes nothing

---

1. Algorithm & Pseudocode

Brute force

repeat until no change:
    remove every occurrence of "()", "[]", "{}" from s
return s is empty

Optimal (stack)

stack = empty stack of characters

for each char c in s:
    if c is an opening bracket:
        push the MATCHING CLOSING bracket onto the stack
    else:
        if stack is empty          → return false   // closes nothing
        if stack.pop() != c        → return false   // wrong type / wrong order

return stack.isEmpty()             // leftovers = unclosed brackets

---

2. Step-by-Step Analysis (Beginner-Friendly)

1. Why the brute force works but is bad Repeatedly deleting adjacent matched pairs eventually collapses a valid string to "". But each pass is O(n) and you may need O(n) passes ("((((...))))") → O(n²), plus String is immutable in Java so every deletion allocates a new string. Correct, wasteful.

2. The ordering insight When you see a ), the only bracket it is allowed to close is the most recently opened unclosed bracket. “Most recent unresolved thing” is exactly what a stack’s top holds. You never search — the answer is at peek().

3. The push-the-closer trick Instead of pushing ( and then writing a matches(open, close) helper with a 3-way if-chain, push the character you expect to see: on ( push ). Then closing is a single stack.pop() != c equality check. Less code, fewer places to typo.

4. Three distinct failure modes — check all three

   • Stack empty when a closer arrives → the closer matches nothing (")(").
   • Popped expectation ≠ the closer → wrong type or wrong nesting ("(]", "([)]").
   • Stack non-empty at the end → something was never closed ("("). Candidates routinely forget the third one.

5. Early exit on odd length A valid string must have even length. if ((s.length() & 1) == 1) return false; is a free O(1) rejection — cheap, and it shows you think about invariants.

---

3. The Dry Run

s = "{[]}"

i	c	Action	Stack (top → bottom)
0	{	opener → push expected }	}
1	[	opener → push expected ]	] }
2	]	closer → pop() = ] ✓ match	}
3	}	closer → pop() = } ✓ match	(empty)

Loop ends, stack empty → true ✓

Contrast — s = "([)]":

i	c	Action	Stack
0	(	push )	)
1	[	push ]	] )
2	)	pop() = ] ≠ ) → return false	—

The stack caught the bad nesting, not just a bad type. ✓

---

4. Java Solution

Brute Force

class Solution {
    public boolean isValid(String s) {
        int prevLength;
        do {
            prevLength = s.length();
            s = s.replace("()", "").replace("[]", "").replace("{}", "");
        } while (s.length() != prevLength);   // loop until nothing more collapses
        return s.isEmpty();
    }
}

Time O(n²) · Space O(n) per pass (String is immutable — each replace allocates)

Optimal

class Solution {
    public boolean isValid(String s) {
        if ((s.length() & 1) == 1) return false;          // odd length can never balance

        Deque<Character> stack = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            switch (c) {
                case '(' -> stack.push(')');              // push the EXPECTED closer
                case '[' -> stack.push(']');
                case '{' -> stack.push('}');
                default  -> {                             // c is a closing bracket
                    if (stack.isEmpty() || stack.pop() != c) return false;
                }
            }
        }
        return stack.isEmpty();                           // leftovers = unclosed
    }
}

Time O(n) — one pass, O(1) per character · Space O(n) — all-openers input "((((("

Pre-Java-14 (no arrow switch), the same logic with a plain if/else chain is equally fine:

if (c == '(' || c == '[' || c == '{') {
    stack.push(c == '(' ? ')' : c == '[' ? ']' : '}');
} else if (stack.isEmpty() || stack.pop() != c) {
    return false;
}

---

5. The “Java vs. Others” Edge

• ArrayDeque over java.util.Stack — Stack extends Vector, so every push/pop is synchronized (pure overhead in single-threaded code) and it iterates bottom-to-top, the reverse of stack order. The JDK docs themselves recommend Deque.
• stack.pop() != c unboxes correctly here. pop() returns Character, c is char, so Java unboxes and compares primitives — safe. Beware the trap: comparing two Character objects with != compares references, and the Character cache only covers 0–127. Keeping one side a primitive char sidesteps it entirely.
• s.toCharArray() allocates a copy. For a tight loop you can use s.charAt(i) instead — no allocation, and charAt is a JIT intrinsic. Either is fine at n = 10^4; know the tradeoff.
• (s.length() & 1) == 1 — bitwise parity check. % 2 is equally fast after JIT; the bitwise form just signals fluency.
• String.replace returns a new String — Java strings are immutable, which is precisely why the brute force is O(n²) in allocations as well as time.

---

6. Complexity Summary

Approach	Time	Space	Notes
Repeated replace	O(n²)	O(n)	Re-scans and reallocates each pass
Stack	O(n)	O(n)	One pass; O(1) work per char
Counter only (( ) alone)	O(n)	O(1)	Only valid with a single bracket type

Follow-up worth volunteering: if there were only one bracket type, a single int counter would do it in O(1) space. Three types force a stack, because you must remember the order, not just the count.

---

Related Problems

#	Problem	Difficulty	Connection
LC 32	Longest Valid Parentheses	Hard	stack of indices, seeded with -1
LC 921	Minimum Add to Make Parentheses Valid	Medium	counter suffices — one type
LC 1249	Minimum Remove to Make Valid Parentheses	Medium	stack of indices to delete
LC 394	Decode String	Medium	two stacks: repeat counts + partial strings
LC 71	Simplify Path	Medium	stack of path segments; .. pops