Contains Duplicate (LC 217)

Pattern: Hashing / Frequency Maps
Difficulty: Easy
Key Concept: A duplicate exists if we ever see a value we have already stored in a set (or if any frequency exceeds one).

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

• nums — integer array

Output

• true if there is at least one duplicate, else false

---

1. Algorithm & Pseudocode

Brute force (nested loops)

FOR i from 0 to nums.length - 1:
    FOR j from i + 1 to nums.length - 1:
        IF nums[i] == nums[j]:
            RETURN true
RETURN false

Optimal (HashSet)

CREATE empty HashSet seen
FOR each x in nums:
    IF seen.add(x) returns false:   // already present
        RETURN true
RETURN false

Middle ground (sort)

SORT nums (copy if you must not mutate)
FOR i from 1 to length - 1:
    IF nums[i] == nums[i - 1]:
        RETURN true
RETURN false

---

2. Step-by-Step Analysis (Beginner-Friendly)

Why nested loops work?
We compare every pair. If any pair matches, we have a duplicate. This is correct but slow for large (n).

Why use a HashSet?
A set remembers which values we have seen. Each lookup/insert is (O(1)) on average, so one pass over the array is enough.

Why does add returning false mean duplicate?
HashSet.add(e) returns true if e was not already in the set, and false if it was. So false immediately signals a duplicate—no separate contains call.

Why sorting works?
Equal values become adjacent after sorting, so one linear scan finds duplicates. Trade-off: (O(n \log n)) time, often less extra memory than a set if you sort in place (but mutates the array).

---

3. The Dry Run

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

Optimal — HashSet seen, using add return value:

Step	Index	x	seen.add(x) returns	seen (after step)	Action / note
1	0	1	true (new)	{1}	Continue
2	1	2	true (new)	{1, 2}	Continue
3	2	3	true (new)	{1, 2, 3}	Continue
4	3	1	false (already)	{1, 2, 3}	Return true

Brute force (first duplicate found): pairs (0,3) both value 1 → duplicate → true.

---

4. Java Solution

Brute Force

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

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

Optimal

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

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 for hash operations.
Space: (O(n)) for the set in the worst case (all distinct).

Sorting variant (middle ground):

import java.util.Arrays;

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)) or (O(\log n)) sort stack, depending on implementation.

---

5. The “Java vs. Others” Edge

• HashSet.add() returns boolean: Lets you write a compact loop: if (!seen.add(x)) return true;. Very idiomatic in Java.
• C++: unordered_set::insert(x).second is false if x was already there; or use count(x) before insert.
• Python: x in seen then seen.add(x), or build a set from the list and compare len(set(nums)) < len(nums).
• Sorting: Mutates nums in the snippet above; clone first if the caller must keep the original order.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	(O(n^2))	(O(1))	Nested loops; no extra structure.
Optimal (HashSet)	(O(n))*	(O(n))	*Average case; worst-case hash maps can degrade.
Sorting	(O(n \log n))	(O(1))~	In-place sort; detects duplicates by adjacent equality.