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:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
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 '()[]{}'.

Edge Cases & Clarifying Questions

Empty String: Although the constraints specify s.length >= 1, handling an empty string (returning true) is a common clarifying question.
Only Opening/Closing Brackets: E.g., ((( or ))). The stack will either be non-empty at the end or we will try to pop from an empty stack.
Interleaved Brackets: E.g., ([)]. The most recently opened bracket [ must be closed before the older ( can be closed.

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

Brute Force Approach

The naive approach is to repeatedly find and remove adjacent matching pairs (e.g., (), [], {}) from the string until no more pairs can be found. If the string becomes empty, it’s valid. This approach involves string shifting and takes O(N^2) time, which is highly inefficient for large inputs.

Optimized LIFO

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.

Common Pitfalls

Forgetting to check if the stack is empty at the end: Even if all popped brackets match, there might be leftover opening brackets (e.g., ((()).
Popping from an empty stack: Encountering a closing bracket when the stack is empty (e.g., )) will cause an error or exception if not handled.
Using synchronized data structures: In Java, using java.util.Stack incurs synchronization overhead. ArrayDeque is the modern, faster alternative.

Java

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();
}

Go

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²)`	`O(N)`	Heavy stack frame overhead for deep nesting.