020. Valid Parentheses

At a Glance

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

Problem (one-liner)

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

Recognition Cues

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

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

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