LeetCode · #20

Valid Parentheses Solution

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

Section One · Problem

Problem Statement

🏷️

Difficulty

Easy

🔗

LeetCode

Problem #20

🏗️

Pattern

Stack — bracket matching

A string is valid if: (1) open brackets are closed by the same type of bracket, (2) open brackets are closed in the correct order, and (3) every close bracket has a corresponding open bracket of the same type.

Example 1

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

Example 2

 Input: s = "(]" Output: false 

Example 3

 Input: s = "([)]" Output: false // Interleaved — wrong nesting order 

Constraints

• 1 ≤ s.length ≤ 10⁴ • s consists of parentheses only: '()[]{}'

Section Two · Approach 1

Brute Force — Repeated Replace

Repeatedly scan the string and remove adjacent matching pairs (), [], {}. If the string becomes empty, it's valid. Each pass removes at most n/2 pairs, so up to n/2 passes → O(n²).

Problem: O(n²) from repeated string scanning. A stack processes every character in a single O(n) pass — push openers, pop and match closers.

Java — Repeated Replace

 class Solution {
public boolean isValid(String s) {
int prev = -1;
while (s.length() != prev) {
            prev = s.length();
            s = s.replace("()", "").replace("[]", "").replace("{}", "");
        }
return s.isEmpty();
    }
}

Python — Repeated Replace

 class Solution:
def isValid(self, s: str) -> bool:
while '()' in s or '[]' in s or '{}' in s:
            s = s.replace('()', '').replace('[]', '').replace('{}', '')
return s == '' 

Metric	Value
Time	O(n²)
Space	O(n) — string copies

Section Three · Approach 2

Stack — O(n)

Scan left to right. When you see an opening bracket, push it onto the stack. When you see a closing bracket, pop the stack and check if the popped opener matches. If the stack is empty when you try to pop, or the bracket doesn't match, it's invalid. At the end, the stack must be empty.

💡 Mental model: Think of stacking plates. Each opening bracket adds a plate. Each closing bracket takes a plate off — but only if it's the right color. If you try to remove a plate that doesn't match, or there are no plates to remove, the stack is broken. At the end, a clean table (empty stack) means everything matched.

Algorithm

Step 1: Create an empty stack and a map: { ')':'(', ']':'[', '}':'{' }.
Step 2: For each character: if it's an opener, push it. If it's a closer, pop and check match.
Step 3: If stack is empty on pop or pop doesn't match → return false.
Step 4: After scanning, return stack.isEmpty().

🎯 When to recognize this pattern:

Any problem involving matching nested pairs — parentheses, HTML tags, function calls — think stack.
The LIFO property naturally handles nesting: the most recently opened thing must be closed first.

Section Four · Trace

Visual Walkthrough

Trace through s = "{[()]}":

Stack — push openers, pop and match closers

Section Five · Implementation

Code — Java & Python

Java — Stack

 import java.util.Stack;
import java.util.Map;
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
Map<Character, Character> map = Map.of(')', '(', ']', '[', '}', '{');
for (char c : s.toCharArray()) {
if (map.containsKey(c)) { // closer if (stack.isEmpty() || stack.pop() != map.get(c))
return false;
            } else {
                stack.push(c); // opener
}
        }
return stack.isEmpty();
    }
}

Python — Stack

 class Solution:
def isValid(self, s: str) -> bool:
        stack = []
        match = {')': '(', ']': '[', '}': '{'}
for c in s:
if c in match:
if not stack or stack.pop() != match[c]:
return False else:
                stack.append(c)
return len(stack) == 0 

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Repeated Replace	O(n²)	O(n)	Simple but slow string rebuilds
Stack ← optimal	O(n)	O(n)	One pass. Stack holds at most n/2 openers.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Odd length	`"("`	Odd-length strings are always invalid — brackets come in pairs.
Single pair	`"()"`	Minimal valid input.
Closer first	`")"`	Stack empty on first pop → false.
Wrong nesting	`"([)]"`	Pop gives '[' but closer is ')' → mismatch.
Deep nesting	`"(((())))"`	Stack grows to n/2, then unwinds. Valid.

⚠ Common Mistake: Forgetting to check stack.isEmpty() at the end. A string like "((" passes all pop checks (no closers to fail) but leaves unmatched openers on the stack. The final empty check catches this.

← Back to Stack problems

LearningTree

LC 20 · Valid Parentheses — Solution & Explanation | DSA Guide