Problem Statement

Valid Parentheses

You are given a string s made only of these six characters: '(', ')', '{', '}', '[' and ']'. Your job is to decide if the brackets are arranged correctly. The string is valid when three things are true. Every open bracket is closed by a bracket of the same type. Brackets are closed in the right order, so the one you opened most recently is the one you close first. And every closing bracket has a matching opening bracket of the same type before it.

easyArrayDictionaryStackStackTime: O(n) · Space: O(n)

Translate the prompt

Every closing bracket must match the most recent unmatched opener. You scan left-to-right once and decide valid or invalid at the end.

Signals to notice

matching bracketsnested pairsLIFO ordering

Brute force first

Repeatedly scan the string and delete any adjacent `()`, `[]`, or `{}` pair. Valid iff the whole string collapses to empty. Each pass only removes innermost pairs, so worst case is O(n²).

The key insight

The most recent unmatched opener is always the next bracket that has to close. That is exactly the LIFO discipline of a stack, so a stack maps 1-to-1 to the constraint.

Trace it on `({[]})`

(   push         → stack: [(
{   push         → stack: [( {
[   push         → stack: [( { [
]   pop matches  → stack: [( {
}   pop matches  → stack: [(
)   pop matches  → stack: []   ✓ empty → valid

What must stay true

The stack contains exactly the unmatched openers seen so far, in the order they appeared. Nothing else is ever on it.

Shape of the loop

for c in s:
  if c is opener: push c
  elif stack empty or top != match(c): return false
  else: pop
return stack is empty

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Returning true the moment every closer has matched. On input `(((`, every closer (there are none) has matched, but the stack still has three openers — you must check the stack is empty at the end.

Stack Pattern