Valid Parentheses (LC 20)

Pattern: Stack
Difficulty: Easy
Key Concept: Each closing bracket must match the most recent unmatched opening bracket—LIFO order.

Problem Statement

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

A string is valid if:

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

Input

• s: String

Output

• boolean — true if valid, else false

Example

• "()" → true
• "()[]{}" → true
• "(]" → false
• "([)]" → false

---

1. Algorithm & Pseudocode

Brute force

Repeatedly remove adjacent matching pairs (), [], {} until no change—like reducing a string. Each scan is O(n), possibly O(n) rounds → O(n²).

while s contains "()" or "[]" or "{}":
    remove one occurrence
return s is empty

Optimal

Use a stack of expected closing characters (or opening chars, then match on close).

stack = empty
for ch in s:
    if ch is opening:
        push matching closing ')'}]' onto stack
    else:
        if stack empty or stack.pop() != ch:
            return false
return stack is empty

---

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

1. Why stack The last opening bracket must close first — last-in-first-out.

2. Why push closing char On '(', push ')' so when you see ')', you compare directly without a big switch.

3. Early exit If you see a closing with an empty stack, it’s invalid immediately.

4. Final check If the string ends but the stack still holds expected closings, there were unmatched opens.

---

3. The Dry Run

Sample: s = "({[]})".

read	action	stack (bottom → top)
(	push )	)
{	push }	), }
[	push ]	), }, ]
]	pop, matches	), }
}	pop, matches	)
)	pop, matches	empty

Result: valid.

ASCII

( { [ ] } )
^ push ) } ]

match ] closes [
match } closes {
match ) closes (

Invalid sample: "([)]" — after [, next ) tries to close [ but top expects ].

---

4. Java Solution

Brute Force

class Solution {
    public boolean isValid(String s) {
        StringBuilder sb = new StringBuilder(s);
        boolean changed = true;
        while (changed) {
            changed = false;
            for (int i = 0; i + 1 < sb.length(); i++) {
                char a = sb.charAt(i);
                char b = sb.charAt(i + 1);
                if ((a == '(' && b == ')') || (a == '[' && b == ']') || (a == '{' && b == '}')) {
                    sb.delete(i, i + 2);
                    changed = true;
                    break;
                }
            }
        }
        return sb.length() == 0;
    }
}

Time: O(n²) worst case (each pass removes one pair).
Space: O(n) for the builder.

Optimal

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public boolean isValid(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                stack.push(')');
            } else if (c == '[') {
                stack.push(']');
            } else if (c == '{') {
                stack.push('}');
            } else {
                if (stack.isEmpty() || stack.pop() != c) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

Time: O(n).
Space: O(n) worst-case stack depth.

---

5. The “Java vs. Others” Edge

• ArrayDeque over Stack Stack extends Vector and is considered legacy; ArrayDeque is faster and purpose-built for LIFO.
• Deque.push/pop Operate on the front as stack top—idiomatic Java.
• C++ std::stack<char> is the direct analog.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute (repeated removal)	O(n²)	O(n)	Simple but slow.
Stack	O(n)	O(n)	Standard linear-time solution.