01. Valid Parentheses

Difficulty:EasyPattern:Stack LIFO MatchingTime:O(n)Space:O(n)

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

How It Works & Algorithmic Design

This uses a Stack Data Structure for LIFO (Last-In, First-Out) matching:

Matching Map: Define a map of closing brackets to their corresponding opening brackets (')': '(', '}' : '{', ']': '[').
Stack Operations: Iterate through character ch in string s:
- If ch is an opening bracket ((, {, [), push it onto the stack.
- If ch is a closing bracket, check the stack top. If the stack is empty or stack.pop() does not equal the matching opening bracket, the string is invalid (return false).
Final Check: After processing all characters, return true if stack.length === 0 (all opened brackets were closed).

Why This Approach Works Best

Parentheses nesting follows a LIFO sequence. A stack processes nesting levels naturally in $O(n)$ time complexity and $O(n)$ auxiliary space.

Example Walkthrough

Input: "()[]{}"

Valid balanced string.

Stack Trace: Push '(' -> Pop '(' on ')' | Push '[' -> Pop '[' on ']' | Push '{' -> Pop '{' on '}'

Stack becomes empty at end.

Output: true

Balanced brackets.

Answer: Valid Parentheses using Stack

function isValid(s) {
  const stack = [];
  const map = { ')': '(', '}': '{', ']': '[' };
  for (const ch of s) {
    if (ch in map) {
      if (stack.pop() !== map[ch]) return false;
    } else {
      stack.push(ch);
    }
  }
  return stack.length === 0;
}

💡 Push opening brackets and match closing brackets using LIFO stack evaluation.

Key Takeaways

Stack data structure handles nested structures naturally.
Always check for empty stack conditions before popping.
Runs in $O(n)$ time and $O(n)$ space.