Valid Parentheses

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

A string is valid if every opening bracket is closed by the same type of bracket and in the correct order.

Why this is worth learning

The stack stores unmatched openings in nesting order. Counts alone cannot distinguish properly nested brackets from crossing pairs.

Before coding: one-minute experiment

Why is "([)]" invalid despite having one opening and closing of each type?

Function signature

func IsValidParentheses(s string) bool

Inputs / outputs

• s: string of bracket characters.
• Return: true if valid, else false.

Example

s = "()[]{}" -> true
s = "(]" -> false

Constraints

• 0 <= len(s) <= 100_000

Core idea (near-solution)

Use a stack of opening brackets. When you see a closing bracket, the top of the stack must be the matching opening bracket.

Invariant: the stack always contains unmatched opening brackets in order.

Algorithm (step-by-step)

1. Initialize an empty stack.
2. For each character:
   • If it's an opening bracket, push it.
   • If it's a closing bracket, the stack must be non-empty and the top must match; pop it.
3. At the end, the stack must be empty.

Correctness sketch

After processing a prefix, the stack contains exactly its unmatched opening brackets, oldest to newest. An opening extends that list. A closing bracket must match the most recent unmatched opening: matching an earlier one would cross a still-open pair and violate nesting. Thus an empty stack or wrong top proves invalidity, while popping a matching top preserves the invariant. At the end, an empty stack means every opening and closing participated in a correctly nested matching pair. A nonempty stack witnesses openings with no corresponding close. This establishes necessity and sufficiency, including the valid empty string.

Trace (hand walkthrough)

Example input:
s = "()[]{}" -> true
s = "(]" -> false

Walk:
- "()[]{}": push (, pop with ); push [, pop with ]; push {, pop with } -> empty stack
- "(]": push (, next ] mismatches -> false

Pitfalls to avoid

• Not checking for an empty stack before popping.
• Forgetting to verify the stack is empty at the end.

Debugging lens

Test a leading closer, a trailing opener, mixed nesting, and empty input. Compare bracket types, not just stack length.

Complexity

• Time: O(n)
• Extra space: O(n)

Implementation notes (Go)

• The supplied reference uses a []byte stack; all permitted brackets are single-byte ASCII.
• Map closing brackets to their expected opening bracket.

Reconstruction checkpoint

Why is "([)]" invalid despite having one opening and closing of each type?

Return to Stack + Monotonic · Module quiz