LeetCode #20: Valid Parentheses — Master the Stack Pattern

LeetCode Problem: #20 — Valid Parentheses
Difficulty: Easy
Topics: String, Stack
Pattern: Stack / Last-In-First-Out (LIFO)
Series: LeetCode Interview Preparation — From Beginner to Expert

Not every interview problem requires complex algorithms.

Some of the most frequently asked problems are built around a simple data structure that you must recognize quickly.

Valid Parentheses is one of them.

The problem looks simple:

()
[]
{}

But it teaches one of the most important patterns in coding interviews:

The Stack

Once you understand why a stack works here, you'll start recognizing the same pattern in problems involving:

• Parentheses
• Brackets
• Undo operations
• Browser history
• Function calls
• Expression evaluation
• Backtracking
• Monotonic stacks
• Parsing
• Syntax validation

Let's break it down.

The Problem

Given a string containing only these characters:

(
)
{
}
[
]

determine whether the input string is valid.

A string is valid if:

1. Every opening bracket has a corresponding closing bracket.
2. Brackets are closed in the correct order.
3. Every closing bracket matches the most recent unmatched opening bracket.

Examples

Example 1

Input:
"()"

Output:
true

Example 2

Input:
"()[]{}"

Output:
true

Every opening bracket is correctly closed.

Example 3

Input:
"(]"

Output:
false

Why?

Because:

(
]

do not match.

Example 4

Input:
"([{}])"

Output:
true

The brackets are properly nested.

Example 5

Input:
"([)]"

Output:
false

This is an important example.

We have:

(
[
)
]

The ) tries to close ( while [ is still open.

The nesting order is incorrect.

The Important Question

How do we keep track of the most recent opening bracket?

Consider:

"([{}])"

When we read the string:

(
([
([{
([{} 

At each point, the bracket we need to close is the most recently opened bracket.

That means:

Last opened
=
First one that must be closed

This is exactly the behavior of a:

Stack

A stack follows:

LIFO

which means:

Last In, First Out

Think of a stack of plates.

If you put:

Plate A
Plate B
Plate C

on top of each other, you remove:

C
B
A

The most recently added item comes out first.

That's exactly what nested parentheses require.

The Core Idea

We'll maintain a stack of opening brackets.

When we encounter an opening bracket:

(
[
{

we push it onto the stack.

When we encounter a closing bracket:

)
]
}

we check the top of the stack.

If the top matches the closing bracket, remove it.

Otherwise:

invalid

At the end:

stack empty → valid
stack not empty → invalid

Visual Example

Consider:

([{}])

Start:

Stack: []

Read:

(

Push it:

Stack:
(

Read:

[

Push:

Stack:
[
(

Read:

{

Push:

Stack:
{
[
(

Now we encounter:

}

The top is:

{

It matches.

Pop:

Stack:
[
(

Next:

]

Top is:

[

Match.

Pop:

Stack:
(

Next:

)

Top is:

(

Match.

Pop:

Stack:
[]

The stack is empty.

Therefore:

Valid

Brute-Force Thinking

Before jumping to a stack, let's think about what a naive solution might do.

One possible idea is repeatedly removing valid pairs:

()
[]
{}

For example:

"([{}])"

could become:

"([])"

then:

"()"

then:

""

Therefore valid.

But repeatedly scanning and modifying the string can lead to poor performance and unnecessary complexity.

More importantly, it doesn't directly model the structure of the problem.

The stack does.

Why a Stack Is the Natural Solution

The problem has a specific relationship:

Opening brackets
        ↓
Nested structure
        ↓
Most recent opening bracket
        ↓
Must close first
        ↓
LIFO
        ↓
STACK

This is an excellent example of data-structure recognition.

You don't need a complicated algorithm.

You need to choose the right data structure.

Python Solution

def isValid(s):
    stack = []

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

    for char in s:

        if char in pairs:
            if not stack or stack[-1] != pairs[char]:
                return False

            stack.pop()

        else:
            stack.append(char)

    return len(stack) == 0

This is the standard approach.

Understanding the Code

Let's break it down.

Step 1: Create a Stack

stack = []

Python lists work well as stacks.

We use:

append()

to push.

And:

pop()

to remove the top element.

Step 2: Create the Matching Map

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

This lets us quickly determine which opening bracket should match a closing bracket.

For example:

pairs[')'] → '('
pairs[']'] → '['
pairs['}'] → '{'

Step 3: Process Each Character

for char in s:

For every character, we determine whether it's:

Opening bracket

or:

Closing bracket

Step 4: Handle Closing Brackets

if char in pairs:

If the character is a closing bracket, we need to find its corresponding opening bracket.

First:

if not stack:
    return False

Why?

Consider:

")"

There is no opening bracket available to match it.

Therefore the string is invalid.

Step 5: Check the Top

stack[-1] != pairs[char]

The top of the stack must be the correct opening bracket.

For:

"([)]"

when we reach:

)

the stack is:

[
(

Actually, the top is:

[

But ) requires:

(

Therefore:

[ != (

and we return:

False

Step 6: Pop Matching Brackets

If the brackets match:

stack.pop()

The opening bracket has now been successfully closed.

Step 7: Handle Opening Brackets

If the character isn't a closing bracket, it's an opening bracket.

We push it:

stack.append(char)

Step 8: Check the Final Stack

At the end:

return len(stack) == 0

Why?

Consider:

"((("

There are three unmatched opening brackets.

The stack contains:

(
(
(

Therefore:

stack != []

and the string is invalid.

Dry Run #1

Input:

"()[]{}"

Character 1

(

Stack:

[
    (
]

Character 2

)

Top:

(

Matches.

Pop.

Stack:

[]

Character 3

[

Push.

Stack:

[

Character 4

]

Matches.

Pop.

Stack:

[]

Character 5

{

Push.

Character 6

}

Matches.

Final stack:

[]

Result:

True

Dry Run #2

Input:

"([)]"

Process:

(

Stack:

(

Then:

[

Stack:

[
(

Then:

)

Expected:

(

But top is:

[

Mismatch.

Therefore:

False

We don't even need to process the remaining characters.

Dry Run #3

Input:

"((()))"

Stack progression:

(
( (
( ( (
( ( 
(
[]

More clearly:

Read ( → [(]
Read ( → [(, (]
Read ( → [(, (, (]
Read ) → [(, (]
Read ) → [(]
Read ) → []

Final stack is empty.

Therefore:

True

Complexity

We process every character once.

For each character, we perform constant-time operations:

append()
pop()
lookup

Therefore:

Time Complexity

O(n)

where n is the length of the string.

Space Complexity

In the worst case, all characters are opening brackets:

"((((((("

The stack can contain n characters.

Therefore:

O(n)

space.

Can We Do Better Than O(n) Time?

No.

At minimum, we need to inspect the input.

For example, the invalid character could be at the very end:

"((((((((((((((((((]"

We cannot know the answer without examining the relevant characters.

Therefore:

O(n)

is optimal asymptotically.

The Most Important Pattern

The pattern isn't just:

parentheses → stack

The bigger pattern is:

When the most recently encountered item must be processed first, think Stack.

This applies to many problems.

Pattern Recognition

Look for phrases such as:

"Most recent"

Most recently opened
Most recently added
Most recent operation

Think:

STACK

"Undo"

For example:

Type A
Type B
Type C
Undo

The most recent action is undone first.

That's LIFO.

"Nested"

Examples:

((()))
[({})]
HTML tags
Programming language syntax

Nested structures often involve stacks.

"Previous unmatched element"

This is another strong signal.

Problems asking you to remember previous elements that haven't been resolved yet often point toward stacks.

Common Mistake #1: Only Checking Counts

A common incorrect idea is:

Number of '(' == number of ')'

That isn't enough.

Consider:

")("

There is:

1 opening
1 closing

but the string is invalid.

Order matters.

That's why a stack is required.

Common Mistake #2: Checking Only Matching Characters

Another mistake is checking whether the string contains valid pairs somewhere.

For example:

"([)]"

contains:

()
[]

but the nesting is wrong.

We need to validate the order.

Common Mistake #3: Forgetting an Empty Stack

Consider:

"]"

If you do:

stack.pop()

without checking whether the stack is empty, you'll get an error.

Always handle:

if not stack:
    return False

Common Mistake #4: Forgetting the Final Stack Check

Consider:

"("

Nothing mismatched during processing.

But the opening bracket was never closed.

Therefore the final stack must be empty.

Common Mistake #5: Using a Queue

A queue follows:

FIFO

First In, First Out.

But nested brackets require:

LIFO

Last In, First Out.

That's why a queue doesn't naturally solve this problem.

Stack Implementation in Python

A Python list can act as a stack.

Push

stack.append(value)

Peek

stack[-1]

Pop

stack.pop()

Check Empty

if not stack:

These four operations are worth memorizing.

Alternative Implementation

You can also use a mapping from opening brackets to closing brackets:

def isValid(s):
    stack = []

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

    for char in s:

        if char in pairs:
            stack.append(pairs[char])

        else:
            if not stack or stack.pop() != char:
                return False

    return not stack

This version has an interesting idea.

Instead of storing the opening bracket, we store the expected closing bracket.

For example:

(

pushes:

)

Then when we encounter:

)

we simply compare it with the top.

Both approaches are valid.

Which Version Should You Use in an Interview?

Either is fine.

The first version is arguably easier to explain because the stack directly contains opening brackets:

(
[
{

The second version is compact and elegant.

During an interview, prioritize:

1. Correctness
2. Clear explanation
3. Complexity
4. Clean implementation

Don't optimize for the fewest lines of code.

Interview Follow-Up Questions

Once you've solved Valid Parentheses, interviewers can make the problem significantly harder.

Follow-Up 1: Longest Valid Parentheses

Instead of checking whether parentheses are valid, find the length of the longest valid substring.

This leads to:

LeetCode #32 — Longest Valid Parentheses

Follow-Up 2: Minimum Additions

How many parentheses must you add to make a string valid?

This tests whether you understand unmatched opening and closing brackets.

Follow-Up 3: Remove Invalid Parentheses

Remove the minimum number of invalid parentheses to make the expression valid.

This introduces more advanced:

BFS
DFS
Backtracking

Follow-Up 4: Min Stack

Design a stack that supports:

push()
pop()
top()
getMin()

all efficiently.

This leads to:

LeetCode #155 — Min Stack

Follow-Up 5: Evaluate Reverse Polish Notation

Use a stack to evaluate mathematical expressions.

This leads to:

LeetCode #150 — Evaluate Reverse Polish Notation

Real-World Applications of Stacks

Stacks aren't just interview concepts.

They appear throughout software engineering.

Function Calls

When functions call other functions:

main()
 ↓
login()
 ↓
validate()
 ↓
database()

the runtime maintains call-stack information.

Undo/Redo

Editors can maintain operations using stacks.

Action A
Action B
Action C

Undo:

C

then:

B

then:

A

Browser Navigation

History can be modeled using stack-like structures.

Expression Parsing

Compilers and interpreters use stack-based techniques to process expressions and nested structures.

Backtracking

Problems such as:

• Maze solving
• DFS
• Permutations
• Combinations
• Sudoku

often rely on stack behavior either explicitly or through recursion.

Stack vs Queue

This distinction is extremely important for interviews.

Remember:

STACK
Last In → First Out

QUEUE
First In → First Out

A Simple Mental Model

Whenever you're unsure whether you need a stack, ask:

"If I encounter something now, will I need to resolve the most recent unresolved thing first?"

If yes:

Think Stack.

For parentheses:

(
[   ← latest opening
{

When a closing bracket appears, { must be handled first.

Exactly what a stack does.

Interview Explanation Template

If an interviewer asks you to explain your solution, you can structure your answer like this:

"I'll use a stack because brackets are nested and the most recently opened bracket must be closed first. I'll push every opening bracket onto the stack. When I encounter a closing bracket, I'll verify that the stack isn't empty and that its top matches the corresponding opening bracket. If it doesn't match, the string is invalid. After processing the entire string, the stack must be empty for the string to be valid. This takes O(n) time and O(n) space."

That's concise, technically accurate, and demonstrates that you understand why a stack is appropriate.

Pattern Library So Far

Our interview pattern library is growing.

LeetCode #1 — Two Sum

Hash Map

LeetCode #121 — Best Time to Buy and Sell Stock

Running Minimum
Greedy

LeetCode #217 — Contains Duplicate

Hash Set

LeetCode #53 — Maximum Subarray

Kadane's Algorithm

LeetCode #167 — Two Sum II

Two Pointers

LeetCode #15 — 3Sum

Sorting
+
Two Pointers

LeetCode #20 — Valid Parentheses

Stack

Notice what we're building.

We're not simply collecting LeetCode solutions.

We're building a mental library of patterns.

Interview Cheat Sheet

Problem:
Validate parentheses/brackets.

Pattern:
Stack.

Why?
Most recently opened bracket
must be closed first.

Opening bracket:
push()

Closing bracket:
check stack top

If mismatch:
return False

If match:
pop()

At the end:
stack must be empty.

Time:
O(n)

Space:
O(n)

Practice Challenges

Before moving forward, try solving these without looking at the solution.

Challenge 1

Check:

"({[]})"

Is it valid?

Challenge 2

Check:

"([)]"

Is it valid?

Explain exactly where it fails.

Challenge 3

Check:

"((()))"

Trace the stack after every character.

Challenge 4

Check:

"{[("

What does the final stack tell you?

Challenge 5

Implement the solution without using a dictionary.

Challenge 6

Design a stack supporting:

push
pop
peek
getMin

in O(1) time.

Final Takeaway

LeetCode #20 looks like a simple parentheses problem.

But it teaches a fundamental interview skill:

Choose the data structure based on the behavior the problem requires.

Here, the requirement is:

Last opened
    ↓
First closed

That is:

LIFO

And LIFO means:

STACK

The complete reasoning becomes:

Nested structure
      ↓
Most recent opening bracket
must be handled first
      ↓
LIFO
      ↓
Stack
      ↓
O(n) time
O(n) space

Once you recognize this pattern, a huge family of problems becomes easier.

The goal isn't to memorize:

stack.append()
stack.pop()

The goal is to look at a problem and immediately ask:

"What behavior does my data structure need to provide?"

That's the kind of pattern recognition that turns LeetCode practice into actual interview preparation.