Valid Parentheses

[!NOTE] This module explores the core principles of the Valid Parentheses problem, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. Problem Definition

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

An input string is valid if:

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

Examples

• Input: s = "()" → Output: true
• Input: s = "([)]" → Output: false
• Input: s = "([])" → Output: true

Constraints

• 1 <= s.length <= 10^4
• s consists of parentheses only '()[]{}'.

---

2. Interactive Analysis

Watch how the Stack handles nested structures. Note how the most recently opened bracket must be the first one matched.

Current: ({[]})

STACK (LIFO)

Click 'Next Step' to step through the algorithm.

---

3. Solutions

Intuition: The Genesis

The problem is identifying nested dependencies. In any nested structure (HTML tags, JSON, Parentheses), the “most recently opened” context is the “first one closed”. This is the pure definition of LIFO. By using a stack, we effectively “checkpoint” opening brackets and verify them when we see a closing one.

Java

Go

public boolean isValid(String s) {
    // ArrayDeque is faster than Stack class (no synchronization overhead)
    Deque<Character> stack = new ArrayDeque<>();

    for (char c : s.toCharArray()) {
        // Map current bracket to its expected closing partner
        if (c == '(') stack.push(')');
        else if (c == '{') stack.push('}');
        else if (c == '[') stack.push(']');
        else {
            // If it's a closing bracket, it MUST match the top of stack
            if (stack.isEmpty() || stack.pop() != c) {
                return false;
            }
        }
    }

    // Valid only if all "promises" were fulfilled
    return stack.isEmpty();
}

func isValid(s string) bool {
    // Standard Go slice as a stack
    stack := make([]rune, 0)

    // Mapping closing to opening for lookup
    pairs := map[rune]rune{
        ')': '(',
        '}': '{',
        ']': '[',
    }

    for _, char := range s {
        if open, isClosing := pairs[char]; isClosing {
            // Closing bracket check
            if len(stack) == 0 || stack[len(stack)-1] != open {
                return false
            }
            stack = stack[:len(stack)-1] // Pop
        } else {
            // Opening bracket
            stack = append(stack, char)
        }
    }

    return len(stack) == 0
}

---

4. Complexity Analysis

Strategy	Time Complexity	Space Complexity	Hardware Connection
Stack (Optimal)	O(N)	O(N)	High Cache Locality; uses contiguous memory.
Recursive	O(N^2)	O(N)	Heavy stack frame overhead for deep nesting.