LeetCode #217: Contains Duplicate — Master Hash Sets and Fast Lookup

LeetCode Problem: Contains Duplicate
Difficulty: Easy
Topics: Array, Hash Set, Sorting
Series: LeetCode Interview Preparation — From Beginner to Expert

After solving Two Sum and Best Time to Buy and Sell Stock, it's time to learn another fundamental interview pattern:

Use a Hash Set when you need to quickly determine whether you've already seen a value.

This sounds simple, but duplicate detection is one of the most common concepts you'll encounter in coding interviews.

The real lesson isn't just how to solve LeetCode #217.

It's learning to recognize when a set is the right data structure.

The Problem

You are given an integer array nums.

Return:

true

if any value appears at least twice.

Otherwise, return:

false

Example 1

Input:
nums = [1, 2, 3, 1]

Output:
true

Because 1 appears twice.

Example 2

Input:
nums = [1, 2, 3, 4]

Output:
false

Every number appears exactly once.

Example 3

Input:
nums = [1, 1, 1, 3, 3, 4, 3, 2, 4, 2]

Output:
true

There are several duplicates.

We only need to determine whether at least one exists.

The First Solution: Brute Force

The most straightforward approach is to compare every element with every other element.

For example:

[1, 2, 3, 1]

We could check:

1 vs 2
1 vs 3
1 vs 1  → duplicate!

Brute-Force Python Solution

def containsDuplicate(nums):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] == nums[j]:
                return True

    return False

This works.

But it is inefficient.

Complexity of Brute Force

We potentially compare every pair of elements.

For n elements:

Time Complexity: O(n²)
Space Complexity: O(1)

This becomes expensive for large arrays.

We need a better approach.

The Key Question

Instead of repeatedly comparing elements, ask:

"Have I already seen this number?"

For:

[1, 2, 3, 1]

we process the numbers one at a time.

Start with:

seen = {}

Read:

1

Have we seen 1?

No

Store it.

seen = {1}

Next:

2

Have we seen 2?

No

Store it.

seen = {1, 2}

Next:

3

Not seen.

seen = {1, 2, 3}

Next:

1

Have we seen 1?

YES!

Therefore:

true

We don't need to scan the rest of the array.

Enter the Hash Set

A set stores unique values.

In Python:

seen = set()

We can check whether a value exists using:

if num in seen:

and add it using:

seen.add(num)

This gives us fast average-case lookup.

Optimized Solution

def containsDuplicate(nums):
    seen = set()

    for num in nums:
        if num in seen:
            return True

        seen.add(num)

    return False

This is the solution you should be able to explain confidently in an interview.

Understanding the Code

Let's break it down.

Step 1 — Create a Set

seen = set()

Initially:

{}

Conceptually, it is an empty collection of values we've encountered.

Step 2 — Iterate Through the Array

for num in nums:

We examine every number.

Step 3 — Check Whether It Exists

if num in seen:

If the number is already present, we have found a duplicate.

Step 4 — Store the Number

seen.add(num)

If it hasn't appeared before, remember it.

Step 5 — No Duplicate Found

If we finish the loop without finding a duplicate:

return False

Complete Dry Run

Consider:

nums = [4, 7, 2, 7]

Initially:

seen = {}

Number = 4

Is 4 in seen?

No

Add it:

seen = {4}

Number = 7

Is 7 in seen?

No

Add it:

seen = {4, 7}

Number = 2

Is 2 in seen?

No

Add it:

seen = {4, 7, 2}

Number = 7

Is 7 in seen?

YES

Return:

true

The algorithm immediately stops.

Dry Run Table

Complexity Analysis

We process each element once.

Each set lookup and insertion is O(1) on average.

Therefore:

Time Complexity

O(n)

Space Complexity

O(n)

In the worst case, every number is unique and we store all of them.

Why a Set Instead of a List?

You could technically use a list:

seen = []

and check:

if num in seen:

But membership checking in a list takes:

O(n)

in the worst case.

Doing this for every element gives:

O(n²)

A hash set provides average:

O(1)

membership lookup.

That's why choosing the right data structure matters.

Set vs Hash Map

You learned a hash map in Two Sum.

Now we're using a hash set.

What's the difference?

Hash Map

Stores:

key → value

Example:

{
    2: 0,
    7: 1
}

Useful when you need additional information such as:

• index
• frequency
• associated value

Hash Set

Stores:

value

Example:

{2, 7, 11}

Useful when you only care about:

Does this value exist?

For Contains Duplicate, we don't need the index.

We only need to know whether we've seen the number before.

Therefore:

Set is the cleaner data structure.

Alternative Approach: Sorting

There is another common solution.

Sort the array:

[4, 2, 7, 2]

becomes:

[2, 2, 4, 7]

Now duplicates will appear next to each other.

We can compare adjacent elements.

Sorting Solution

def containsDuplicate(nums):
    nums.sort()

    for i in range(1, len(nums)):
        if nums[i] == nums[i - 1]:
            return True

    return False

If:

nums[i] == nums[i - 1]

then we've found a duplicate.

Complexity of Sorting

Sorting typically takes:

O(n log n)

Then the scan takes:

O(n)

Overall:

O(n log n)

Depending on the sorting implementation and constraints, auxiliary space can vary.

The hash-set solution is generally preferable when extra memory is allowed:

O(n)

time.

Which Solution Should You Give in an Interview?

If the interviewer asks:

"Can you solve it in linear time?"

Immediately think:

Hash Set

Give:

def containsDuplicate(nums):
    seen = set()

    for num in nums:
        if num in seen:
            return True

        seen.add(num)

    return False

Then explain:

"I maintain a set of values I've already encountered. Before inserting each number, I check whether it already exists. Set membership is O(1) on average, so the overall solution is O(n)."

That's a strong interview explanation.

An Even Simpler Python Solution

Python provides a very concise way to solve this:

def containsDuplicate(nums):
    return len(nums) != len(set(nums))

Why does it work?

Suppose:

nums = [1, 2, 3, 1]

Length of array:

4

Set:

{1, 2, 3}

Length of set:

3

Because:

4 != 3

there must be a duplicate.

Should You Use the One-Liner in an Interview?

You can.

But don't make the one-liner your first response.

Interviewers are often evaluating your problem-solving process, not just whether you know Python tricks.

A better approach is:

1. Explain the set-based algorithm.
2. Write the readable solution.
3. Analyze complexity.
4. Mention the concise version if appropriate.

The interviewer should understand that you know why the solution works.

Edge Cases

Empty Array

nums = []

There are no duplicates.

false

One Element

nums = [10]

No duplicate is possible.

false

All Elements Unique

nums = [1, 2, 3, 4, 5]

Answer:

false

Every Element Is the Same

nums = [5, 5, 5, 5]

Answer:

true

The second 5 immediately reveals the duplicate.

Common Mistake #1: Adding Before Checking

Consider:

seen.add(num)

if num in seen:
    return True

This is wrong.

Why?

Because you've already inserted the current number.

It will always be found.

The correct order is:

if num in seen:
    return True

seen.add(num)

First ask:

"Have I seen it?"

Then:

"If not, remember it."

Common Mistake #2: Using a Dictionary Unnecessarily

You could write:

seen = {}

and store values.

But if you don't need associated information, a set communicates your intention more clearly:

seen = set()

Good code isn't only about correctness.

It should also express the algorithm clearly.

Common Mistake #3: Sorting Without Considering Side Effects

The sorting approach modifies the input:

nums.sort()

Sometimes that's perfectly acceptable.

But if the interviewer says:

"Don't modify the input array."

then this approach needs adjustment.

This is why you should always pay attention to constraints.

The Bigger Interview Pattern

The real lesson from this problem is:

When a problem asks whether something has appeared before, think about a Set.

Watch for phrases such as:

• "Contains duplicates"
• "Have we seen this before?"
• "Check whether an element already exists"
• "Find repeated values"
• "Detect duplicates"
• "Find unique elements"
• "Determine whether two values are the same"
• "Track previously encountered elements"

These are strong signals for a hash set.

The Pattern

The general pattern is:

Array
  ↓
Create Set
  ↓
Read current value
  ↓
Already in Set?
  ├── YES → Duplicate found
  └── NO  → Add to Set
  ↓
Continue

This pattern appears in many interview problems.

Connection With Two Sum

Remember our first problem?

Two Sum used:

Hash Map

because we needed:

number → index

Contains Duplicate uses:

Hash Set

because we only need:

number exists?

This is an important progression.

You shouldn't just memorize:

"Two Sum = Hash Map"
"Contains Duplicate = Hash Set"

Instead ask:

What information do I actually need to remember?

If you need:

value + additional information

→ Hash Map.

If you only need:

Does this value exist?

→ Hash Set.

Interview Follow-Up Questions

Once you've solved Contains Duplicate, the interviewer can easily make the problem harder.

Follow-Up 1: Return the Duplicate

Instead of:

true / false

return the duplicate value.

Follow-Up 2: Return All Duplicates

For:

[1, 2, 3, 1, 2]

return:

[1, 2]

Now you need to think about how to avoid reporting the same duplicate multiple times.

Follow-Up 3: Find the Most Frequent Element

Now a set is no longer enough.

You need:

value → frequency

This points toward a Hash Map.

Follow-Up 4: Find the First Duplicate

Order now matters.

You need to think carefully about when a value first repeats.

Follow-Up 5: Solve With Constant Extra Space

Now the interviewer is testing whether you understand the trade-off between:

Time

and:

Space

Depending on the constraints and values involved, completely different techniques may become possible.

A Real Interview Conversation

Imagine the interviewer asks:

Interviewer: How would you solve Contains Duplicate?

You might start:

"The brute-force approach is to compare every pair, which is O(n²). We can do better by maintaining a hash set of values we've already seen."

Then:

"For every number, I first check whether it's already in the set. If it is, I return true. Otherwise, I add it to the set."

Then:

"This gives O(n) average time and O(n) space."

That's concise, technically correct, and demonstrates your reasoning.

What You Should Learn From This Problem

Don't memorize:

seen = set()

Memorize the question that leads to it:

"Do I need to know whether I've seen this value before?"

If the answer is yes:

Think Set.

If you need additional information associated with that value:

Think Hash Map.

That distinction will save you enormous amounts of time in future LeetCode problems.

Interview Cheat Sheet

Problem:
Determine whether an array contains duplicates.

Brute Force:
Compare every pair.

Time:
O(n²)

Optimized:
Use a Hash Set.

For every number:

    If number is already in set:
        return True

    Add number to set.

If loop finishes:
    return False

Time:
O(n) average

Space:
O(n)

Practice Challenges

Before moving to the next problem, try these variations:

Challenge 1

Return the first duplicate number.

Challenge 2

Return all duplicate numbers.

Challenge 3

Count how many duplicate values exist.

Challenge 4

Find the value that appears most frequently.

Challenge 5

Determine whether two arrays contain any common element.

Challenge 6

Find the intersection of two arrays.

These problems will strengthen your understanding of Hash Sets and Hash Maps.

Final Takeaway

LeetCode #217 looks almost trivial.

But it teaches one of the most useful interview instincts:

Don't repeatedly search through data when you can remember what you've already seen.

The brute-force solution asks:

"Have I seen this value?"

→ Search through previous elements.
→ O(n)

for every element.

The optimized solution asks:

"Have I seen this value?"

→ Hash Set lookup.
→ O(1) average.

Repeated work becomes constant-time lookup.

That's the power of choosing the right data structure.

And this is exactly the kind of thinking that separates someone who knows syntax from someone who can solve problems efficiently in an interview.