Valid Parentheses

Check whether all brackets close in the correct order.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Valid Parentheses: A closing bracket is valid only when it removes its matching newest unmatched opening bracket.

Input and goalCheck whether all brackets close in the correct order.

Initialize an empty stackBefore scanning ([{}]), there is no unmatched opening bracket.

emptytop

input([{}])layoutbottom to topcurrentbefore index 0actioninitialize

Recognize it

Use this pattern when nested delimiters must close in reverse opening order and each closer must validate the most recent unfinished opener.

Keep true

After each processed character, the stack contains exactly the unmatched opening brackets from the processed prefix, ordered oldest at the bottom and newest at the top.

Reuse it

For tags, expression delimiters, and nested scopes, store only unfinished openers and let each closer inspect the newest one; an empty stack at the end proves completion.

Pattern: Stack.

Simple idea: Save opening brackets. A closing bracket must match the newest opening bracket.

def valid_parentheses(text: str) -> bool:
   opening: list[str] = []
   matching = {")": "(", "]": "[", "}": "{"}

   for char in text:
      if char not in matching:
         opening.append(char)
      elif not opening or opening.pop() != matching[char]:
         return False

   return not opening

Cost: $O(n)$ time and $O(n)$ space.