Contains Duplicate

What the problem is really asking

We only need to know whether any value appears more than once.

So this is really a fast membership-check problem.

Intuition

When we read a number, there are only two possibilities:

• we have seen it before
• we have not seen it before

A hash set is perfect for this kind of yes/no lookup.

Brute-force idea

The slow method is to compare every number with every later number.

That means nested loops, which takes O(n^2) time.

Optimized approach

Use a set.

Go through the array once:

1. if the current number is already in the set, return true
2. otherwise insert it and continue

If the loop finishes, no duplicate exists.

import java.util.HashSet;
import java.util.Set;

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> seen = new HashSet<>();

        for (int num : nums) {
            if (!seen.add(num)) {
                return true;
            }
        }

        return false;
    }
}

Dry run

Take nums = [1, 2, 3, 1].

• see 1, insert it
• see 2, insert it
• see 3, insert it
• see 1 again, but it is already in the set

So the answer is true.

Common mistakes

1. Using a list instead of a set

Then membership checks become slow, and the solution loses its advantage.

2. Forgetting the early return

As soon as you see a repeated value, you already know the answer.

3. Overthinking the problem

This is not about counting every value. It is only about detecting whether a repeat exists.

Complexity

Time Complexity: O(n)

Space Complexity: O(n)