Valid Parentheses

Problem Statement

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

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

Approach 1: Brute Force

Explanation: Repeatedly remove pairs of valid parentheses until none remain.

Time Complexity: O(n²)

Space Complexity: O(n) (for string manipulation)

while "()" or "[]" or "{}" exists in s:
    remove all occurrences
if s is empty:
    return true
else:
    return false

💡 Think: What if I repeatedly strip '()','[]','{}' until nothing changes?

Approach 2: Using Stack (Better)

Explanation: Push opening brackets to stack; match closing brackets with top.

Time Complexity: O(n)

Space Complexity: O(n)

stack = empty
for char in s:
    if char is '(', '{', '[':
        push char to stack
    else:
        if stack is empty or top doesn't match char:
            return false
        pop stack
return stack is empty

💡 Think: Can I push opens and match each close with the latest open?

Approach 3: Optimized Stack (Early Return)

Explanation: Use a map for closing brackets; immediately return false on mismatch.

Time Complexity: O(n)

Space Complexity: O(n)

map = {')':'(', '}':'{', ']':'['}
stack = empty
for char in s:
    if char in map.values():
        push char
    else if char in map.keys():
        if stack is empty or stack.pop() != map[char]:
            return false
return stack is empty

💡 Think: Use a map to early-fail when the top doesn't match the closing.

Solve on LeetCode