Contains Duplicate (LC 217)

Pattern: HashSet Membership Check Difficulty: Easy Key Concept: Walk the array, adding each value to a HashSet. If a value is already there, you found a duplicate.

Problem Statement

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

Example

• nums = [1, 2, 3, 1] → true
• nums = [1, 2, 3, 4] → false

---

1. Algorithm & Pseudocode

Brute force

For each i, for each j > i, check nums[i] == nums[j].

Sort + adjacent check

Sort the array. If any nums[i] == nums[i+1], return true.

Optimal — HashSet

1. Create empty HashSet<Integer> seen.
2. For each x in nums:
3. If !seen.add(x) → duplicate found, return true.
4. Return false.

HashSet.add returns false iff the value already existed.

---

2. Step-by-Step Analysis

Why brute force works — exhaustive pair check. Why brute force is slow — (O(n^2)).

Why sort works — duplicates become adjacent. Why sort is suboptimal — (O(n \log n)) and mutates input.

Why HashSet is the right tool A set answers “have I seen this before?” in O(1) average. Walking the array once is enough — as soon as you see a repeat, you can return immediately (no need to finish the scan).

Why seen.add(x) (not contains + add) add() already returns a boolean — saves one hash lookup compared to if(contains) ... else add.

---

3. The Dry Run

nums = [1, 2, 3, 1]

Step	x	seen (before)	add returns	Action
1	1	{}	true	add 1
2	2	{1}	true	add 2
3	3	{1,2}	true	add 3
4	1	{1,2,3}	false	return true

---

4. Java Solution

Brute Force

class Solution {
    public boolean containsDuplicate(int[] nums) {
        for (int i = 0; i < nums.length; i++)
            for (int j = i + 1; j < nums.length; j++)
                if (nums[i] == nums[j]) return true;
        return false;
    }
}

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

Sort

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);
        for (int i = 1; i < nums.length; i++)
            if (nums[i] == nums[i - 1]) return true;
        return false;
    }
}

Time: (O(n \log n)) Space: (O(1)) (in-place sort)

Optimal

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int x : nums) {
            if (!seen.add(x)) return true;
        }
        return false;
    }
}

Time: (O(n)) average Space: (O(n))

---

5. The “Java vs. Others” Edge

• HashSet.add returns boolean — Python’s set.add returns None, so this one-liner is Java-specific.
• For tight memory: use a BitSet if values are bounded and non-negative — uses 1 bit per slot.
• IntStream.of(nums).distinct().count() != nums.length is a one-liner but slower and allocates more.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	(O(n^2))	(O(1))	Pair check
Sort	(O(n \log n))	(O(1))	Mutates input
HashSet	(O(n))*	(O(n))	*Average; worst-case hash O(n²)