020. Valid Parentheses

Quick Identifier

• Topic: stack
• Pattern: Stack Match
• Difficulty: Easy
• Companies: Amazon, Google, Meta, Bloomberg, Microsoft
• Frequency: Very High
• LeetCode: 20

Quick Sights

• Time Complexity: O(n) from the optimal approach.
• Space Complexity: O(n) from the optimal approach.
• Core Mechanism: Given a string of brackets ()[]{}, return whether every opening bracket is closed in correct order and type by a matching closing bracket.

Concept Explanation

Given a string of brackets ()[]{}, return whether every opening bracket is closed in correct order and type by a matching closing bracket.

The key is to state the invariant before coding: what part of the input is already settled, what state is still unresolved, and what single operation makes progress without losing correctness.

Recognition cues:

• "Well-formed parentheses" / nesting
• Last opened must close first (LIFO)
• Use stack of expected closers or openings

Study Pattern (SDE3+)

• 0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
• Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
• 5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Approaches

• Brute force — recursive matching with index — O(n) but heavy constant / stack depth.
• Better — counter tricks fail for ([)] interleaving — do not use single counter.
• Optimal — O(n) time / O(n) space — push expected closer on ( / [ / {, pop and verify on closers.

Optimal Solution

Go

func isValid(s string) bool {
	stack := make([]rune, 0, len(s))
	pair := map[rune]rune{')': '(', ']': '[', '}': '{'}
	for _, ch := range s {
		switch ch {
		case '(', '[', '{':
			stack = append(stack, ch)
		default:
			if len(stack) == 0 {
				return false
			}
			top := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			if pair[ch] != top {
				return false
			}
		}
	}
	return len(stack) == 0
}

JavaScript

function isValid(text) {
	const stack = [];
	const pair = { ')': '(', ']': '[', '}': '{' };
	for (const char of text) {
		if (char === '(' || char === '[' || char === '{') {
			stack.push(char);
		} else {
			if (stack.length === 0) {
				return false;
			}
			const top = stack.pop();
			if (pair[char] !== top) {
				return false;
			}
		}
	}
	return stack.length === 0;
}

Walkthrough

Input: s = "([{}])"

Invariant: stack is exactly the unmatched openers in LIFO order.

Edge Cases

• Empty string (valid by definition in many statements; LeetCode: valid)
• Only openers
• Only closers
• Mismatched size

Pitfalls

• Popping when empty
• Forgetting to check stack empty at end

Similar Problems

• 22. Generate Parentheses — build valid strings.
• 394. Decode String — nested structure with stack.
• 71. Simplify Path — token stack for path segments.

Variants

• Wildcard * as ( or ) or empty — two-stack / range tracking.
• Longest valid parentheses — often DP or stack of indices.

Mind-Map Tags

#stack #parentheses #lifo #matching #brackets