title: Valid Parentheses
slug: valid-parentheses
difficulty: easy
leetcode_id: 20
leetcode_url: https://leetcode.com/problems/valid-parentheses/
categories:
  - strings
  - stack
patterns:
  - slug: monotonic-stack
    is_optimal: true

function_signature: "def is_valid(s: str) -> bool:"

test_cases:
  visible:
    - input: { s: "()" }
      expected: true
    - input: { s: "()[]{}" }
      expected: true
    - input: { s: "(]" }
      expected: false
  hidden:
    - input: { s: "([)]" }
      expected: false
    - input: { s: "{[]}" }
      expected: true
    - input: { s: "((()))" }
      expected: true
    - input: { s: "(" }
      expected: false
    - input: { s: ")(" }
      expected: false

description: |
  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.

constraints: |
  - `1 <= s.length <= 10^4`
  - `s` consists of parentheses only `'()[]{}'`

examples:
  - input: 's = "()"'
    output: "true"
    explanation: "Single pair of matching parentheses."
  - input: 's = "()[]{}"'
    output: "true"
    explanation: "Three separate valid pairs."
  - input: 's = "(]"'
    output: "false"
    explanation: "Mismatched bracket types."
  - input: 's = "([)]"'
    output: "false"
    explanation: "Incorrect nesting order — the inner bracket must close before the outer one."

explanation:
  intuition: |
    Imagine you're reading a book with nested parenthetical comments. Each time you see an opening bracket, you mentally "start" a new thought. When you encounter a closing bracket, it *must* complete the most recent unclosed thought — not some earlier one.

    Think of it like stacking plates: you can only remove the plate on top (last in, first out). The most recently opened bracket must be closed first before you can close any outer brackets.

    This **LIFO (Last-In-First-Out)** behavior is exactly what a stack does! When we see an opening bracket, we push it onto the stack. When we see a closing bracket, we check if it matches the bracket on top of the stack (the most recent unclosed one).

    The key insight is that valid bracket sequences have a **mirror-like property**: if you trace through a valid string, every closing bracket you encounter should match the most recent unmatched opening bracket.

  approach: |
    We solve this using a **Stack-Based Matching Approach**:

    **Step 1: Create a mapping and initialise the stack**

    - Map each closing bracket to its corresponding opening bracket: `{')': '(', '}': '{', ']': '['}`
    - Initialise an empty stack to track unmatched opening brackets

    &nbsp;

    **Step 2: Iterate through each character**

    - If it's an **opening bracket** (`(`, `{`, `[`): push it onto the stack
    - If it's a **closing bracket** (`)`, `}`, `]`):
      - Check if the stack is empty — if so, there's no opening bracket to match, return `False`
      - Check if the top of the stack matches the expected opening bracket — if not, return `False`
      - If it matches, pop the stack (this opening bracket is now matched)

    &nbsp;

    **Step 3: Final validation**

    - After processing all characters, check if the stack is empty
    - An empty stack means every opening bracket found its match
    - A non-empty stack means there are unmatched opening brackets

    &nbsp;

    This works because the stack maintains the order of unmatched opening brackets, and we always match against the most recent one.

  common_pitfalls:
    - title: Forgetting to Check for Empty Stack
      description: |
        When you encounter a closing bracket, you must first check if the stack is empty. Attempting to access `stack[-1]` (or `stack.pop()`) on an empty stack causes an error in most languages.

        For example, with input `")"`, there's no opening bracket to match. The stack is empty, so we should return `False` immediately.
      wrong_approach: "Directly checking stack[-1] without empty check"
      correct_approach: "if not stack or stack[-1] != expected: return False"

    - title: Not Checking Stack at the End
      description: |
        Processing all characters successfully doesn't mean the string is valid! Consider `"((("` — no errors occur during iteration, but we have unmatched opening brackets.

        The string is only valid if the stack is **completely empty** after processing all characters. Returning `True` immediately after the loop is incorrect.
      wrong_approach: "return True after the loop"
      correct_approach: "return len(stack) == 0"

    - title: Mapping Brackets in the Wrong Direction
      description: |
        Map **closing brackets to opening brackets**, not the other way around. We encounter closing brackets when we need to check for a match, so we need to look up what opening bracket it should match.

        Using the wrong direction requires extra logic to reverse the lookup when checking matches.
      wrong_approach: "mapping = {'(': ')', '{': '}'}"
      correct_approach: "mapping = {')': '(', '}': '{'}"

  key_takeaways:
    - "**Stack for nested structures**: Any problem involving matching or nesting (brackets, tags, function calls) likely needs a stack"
    - "**LIFO matches nesting order**: The most recently opened element must close first — this is the defining insight"
    - "**Two-part validation**: Check matches during iteration AND verify empty stack at the end"
    - "**Pattern recognition**: This technique extends to validating HTML tags, code blocks, mathematical expressions, and any nested structure"

  time_complexity: "O(n). We process each character exactly once, and each stack operation (push/pop/peek) is O(1)."
  space_complexity: "O(n). In the worst case (all opening brackets like `(((((`), the stack holds n/2 or n elements."

solutions:
  - approach_name: Stack
    is_optimal: true
    code: |
      def is_valid(s: str) -> bool:
          # Map closing brackets to their opening counterparts
          mapping = {')': '(', '}': '{', ']': '['}

          # Stack to track unmatched opening brackets
          stack = []

          for char in s:
              if char in mapping:
                  # It's a closing bracket — check for match
                  if not stack or stack[-1] != mapping[char]:
                      # Stack empty or top doesn't match
                      return False
                  # Match found, remove the opening bracket
                  stack.pop()
              else:
                  # It's an opening bracket — add to stack
                  stack.append(char)

          # Valid only if all brackets were matched
          return len(stack) == 0
    explanation: |
      **Time Complexity:** O(n) — Single pass through the string with O(1) stack operations.

      **Space Complexity:** O(n) — Stack can hold up to n/2 opening brackets in the worst case.

      We use a stack to track unmatched opening brackets. For each closing bracket, we verify it matches the most recent opening bracket (top of stack). After processing all characters, an empty stack confirms all brackets were properly matched.

  - approach_name: Stack with Early Length Check
    is_optimal: true
    code: |
      def is_valid(s: str) -> bool:
          # Quick optimisation: odd length can never be valid
          if len(s) % 2 != 0:
              return False

          # Map opening brackets to expected closing brackets
          pairs = {'(': ')', '{': '}', '[': ']'}
          stack = []

          for char in s:
              if char in pairs:
                  # Opening bracket — push expected closing bracket
                  stack.append(pairs[char])
              elif not stack or stack.pop() != char:
                  # Closing bracket — must match what we expect
                  return False

          # All brackets must be matched
          return not stack
    explanation: |
      **Time Complexity:** O(n) — Single pass with O(1) operations.

      **Space Complexity:** O(n) — Stack storage.

      This variation pushes the *expected closing bracket* instead of the opening one. When we encounter a closing bracket, we simply compare it directly with `stack.pop()`. The early length check provides a quick exit for obviously invalid inputs.
