20. Valid Parentheses

EasyStack and Expression ProcessingStackMatching stack for bracket pairs

Valid Parentheses

Given a string s containing only the characters '(', ')', '{', '}', '[' and ']', decide whether the string is valid. A string is valid when every opening bracket is closed by the same type of bracket, brackets close in the correct order, and every closing bracket has a matching opening bracket.

Open official problem prompt ↗

In plain English

Decide whether every bracket in the string is properly opened and closed in the correct nested order.

Picture it like this

Think of a stack of plates: you can only remove the top plate. The last bracket you open is the first one you are allowed to close, exactly like the top plate.

Example

Input: s = "()[]{}"
Output: true
Why: Each closing bracket immediately matches the most recent unmatched opening bracket of the same type, and nothing is left over.

Constraints

1 <= s.length <= 10^4s consists only of the characters '()[]{}'

Pattern lesson

See the pattern, then code

Matching stack for bracket pairs

↗

Stack and Expression Processing

Nested structures, matching delimiters, undo behavior, or unresolved operations.. The last opening bracket seen is the first one that must be closed, so a stack of unmatched openers lets you verify each closer against the correct partner in O(1).

New words, made simpleKnow these before the algorithm

Stack: A last-in-first-out container where you only ever add to or remove from one end (the top).
Opening bracket: One of '(', '[', '{' that starts a group.
Matching pair: An opener and closer of the same type, like '(' with ')'.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Repeated pair removal

Rebuilding the string on each pass is quadratic and wasteful.

Repeatedly delete adjacent matched pairs like '()' from the string until nothing changes; valid if the string becomes empty.

Time O(n^2)Space O(n)

Best choiceStack of openers

One linear pass with O(1) checks per character; the natural fit for nested matching.

Push every opener; when a closer appears, it must cancel the opener on top of the stack.

Time O(n)Space O(n)

The rule we keep true

Invariant

The stack always holds, from bottom to top, exactly the opening brackets seen so far that have not yet been closed, in the order they were opened.

Why this is correct

Reasoning

A closer can only be valid against the most recently opened, still-unmatched bracket. Matching it against the stack top and popping preserves the invariant; if the top type differs or the stack is empty, no valid pairing exists. An empty stack at the end means every opener found its closer.

The algorithm in three movesSay these aloud before coding

1Scan each character left to right

push '(' -> stack ['(']

2Push opening brackets onto the stack

')' pops '(' -> match, stack []

3On a closing bracket, pop and confirm it matches; fail if the stack is empty or the types differ

end: stack empty -> true

4After the scan, the string is valid only if the stack is empty

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Read'('

2 · AskOpener or closer?

3 · Update statestack = ['(']

4 · ResultOpener, push it

Key takeaway

Each opener is pushed and popped by its matching closer, leaving the stack empty.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3Closer-to-opener map
Maps each closing bracket to the opener it must cancel, so the match test is a single dictionary lookup.
2
Lines 5-11Single scan
Closers must match the popped top; anything else pushes onto the stack of pending openers.
3
Lines 12Final emptiness check
Leftover openers mean unclosed brackets, so validity requires an empty stack.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Odd-length strings can never be valid
A closing bracket as the very first character (empty stack) must fail
Leftover openers at the end must fail
A single bracket is always invalid

Common beginner mistakes

Forgetting the final empty-stack check and returning true with openers still pending
Popping an empty stack without guarding against it
Comparing only bracket count instead of type and order, which accepts '(]'

Check your understanding

Why is checking that the counts of openers and closers are equal not enough?

Valid Parentheses

Valid Parentheses

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Stack and Expression Processing