Valid Parentheses

LeetCode 20 • Easy • Stack

Input: s = "()[]{}" → Output: true. Use a stack: push open brackets, pop and match on close. Stack empty at end = valid.

TimeO(n)

SpaceO(n)

Index: — Stack: [ ] Result: —

Current char

In stack

Matched

Mismatch

Current —

Stack

[ ]

Result —

Speed:

Ready

Press Play. For each char: if open push; if close pop and match. Empty stack at end = valid.

Whiteboard

Size:3

Type It

Practice until you don't need to look. The green highlights are the nuances.

═══ VALID PARENTHESES — STACK ═══

PATTERN ▸ Stack matching O(n) · O(n)

① INIT

stack = []

pair = {')':'(', ']':'[', '}':'{'}

② LOOP

for c in s:

if c in pair: pop and match

else: push(c)

③ RETURN

return len(stack) == 0

your implementation

Verify: