Contains Duplicate: practice | DSA Trainer

1. Understand the problem

Problem statement

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

Input

An array of integers `nums`.

Output

A boolean. `true` if any number appears at least twice, `false` if all numbers are distinct.

Examples

input → nums = [1, 2, 3, 1]

output → true

1 appears at index 0 and index 3.

input → nums = [1, 2, 3, 4]

output → false

All values are different.

input → nums = [1, 1, 1, 3, 3, 4, 3, 2, 4, 2]

output → true

Multiple values repeat.

Quick check

Before any hints, take a guess.

You're walking through [1, 2, 3, 1]. At each step you need to ask: have I seen this number before? Which structure lets you answer that in O(1)?

Pick an answer to continue

2. Spot the pattern

Before any code, every problem starts with a question. For this problem:

“How would I know if I've seen this number before?”

Each time you pick up a number, you'd naturally ask yourself: have I already come across this one? Once you're asking that, you need something that lets you record what you've passed and check it instantly. That's what a Set is for.

Why not Hash Map?

A Hash Map would work, but it tracks values and positions you don't need. You only care whether a value appeared before, a Set is the simpler, more direct tool.

Quick check

You're coding the set-based solution. Should you check whether n is in the set before adding it, or after?

Pick an answer to continue

3. Brute force idea

For each number, scan the rest of the array to see if that same value appears again. The moment you find a match, return true.

Brute force (the slow one)

O(n²)

for i in 0 .. len(nums) - 1:
    for j in i + 1 .. len(nums) - 1:    # ← the nested loop is the trap
        if nums[i] == nums[j]:
            return true
return false

Why this is too slow

Every element is compared against every element after it. For n numbers that's roughly n × n / 2 comparisons. O(n²). A list of 100,000 numbers means up to 5 billion checks.

Why this is not ideal for interviews

Nested loops are the sign that you haven't spotted the better structure yet. Interviewers want to see you jump to the set-based O(n) approach, it's the canonical answer for 'have I seen this before?' problems.

Time: O(n²)

Space: O(1)

4. Climb the hint ladder

Five rungs. Click for the next one only when you genuinely need it. Each rung is a stronger nudge than the last.

5. The optimized approach

Walk through the array once. For each number, check if it's already in a set. If it is, you have a duplicate, return true. If not, add it to the set and keep going. If you finish the loop, return false.

Pseudocode

seen = empty set

for n in nums:
    if n in seen:
        return true
    seen.add(n)

return false

6. Dry run, row by row

Trace it with the first example: nums = [1, 2, 3, 1].

step	i	nums[i]	in seen?	seen (after)
1	0	1	no	{1}
2	1	2	no	{1, 2}
3	2	3	no	{1, 2, 3}
4	3	1	yes ✓	—

step 1: 1 is new, add it to seen.

step 2: 2 is new, add it.

step 3: 3 is new, add it.

step 4: 1 is already in seen, duplicate found, return true.

Quick check

Two approaches both give the right answer:

(A) A loop that checks each number against a growing set and returns true the moment it finds a match.

(B) Dump the entire array into a set at once, then check if the set is smaller than the array. A set can't hold duplicates, so if the sizes differ, a duplicate existed.

On [1, 1, 2, 3, 4, ...9998] (10,000 numbers, duplicate at index 1), which does less work?

Pick an answer to continue

7. The code

You've seen the pseudocode and the dry run. Try writing the solution yourself in the editor on the right. Run your tests there first. The reveal stays here when you're ready to check.

8. Review & common mistakes

Lock it in

What is the signal that tells you to use the Set pattern? Write it in one sentence, in your own words.

Common mistakes

Sorting first then comparing neighbors
Sorting works (O(n log n)) and is fine to mention, but the set approach is faster and uses the same 'have I seen this' intuition that carries to harder problems. Know both, prefer the set.
Adding to the set before checking
If you add n before checking, you'd need to verify the count is > 1 instead of simply doing 'is it already there?', it's more error-prone. Check first, add second.
Comparing set size to array length
`new Set(nums).size < nums.length` is a cute one-liner but it builds the entire set before telling you anything. The early-return loop stops as soon as it finds a duplicate, which is faster on average.

Pattern family