Contains Duplicate

EasyHashing · Hash Set🧩 Hashing & Counting LeetCode #217 ↗Updated Oct 30, 2026

Problem

You get an integer array nums. Return true if some value occurs two or more times anywhere in it, and false when every element is unique.

Input[4,7,1,7]Outputtrue

Input[5,6,8,9]Outputfalse

Input[2,2,2,3,3]Outputtrue

1 ≤ n ≤ 10⁵ · -10⁹ ≤ nums[i] ≤ 10⁹

Try it yourself

Java

class Solution {
    public boolean containsDuplicate(int[] nums) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

You only need to answer “have I seen this value before?” for each element — a hash set answers that in O(1), and the first repeat ends the scan.

PatternHashing & Counting

Instinct Need "have I seen this before?", "how many times?" or "group things that look alike"? Trade memory for O(1) lookups with a HashMap, HashSet or int[26].

Memory hack Don't search, remember - every element checks in at the front desk, and the desk answers instantly.

Open the Hashing & Counting guide →

Approaches

Brute ForceCompare Every Pair

Time O(n²)Space O(1)

A duplicate is just a pair i < j with equal values. Two nested loops try every such pair and stop at the first match; if none matches, all values are distinct.

Java

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;
}

Zero extra memory, but ~5·10⁹ comparisons at n = 10⁵ — too slow.

BetterSort, then Check Neighbours

Time O(n log n)Space O(n) copy (O(log n) in place)

After sorting, equal values become adjacent, so one pass comparing a[i] with a[i-1] finds any repeat. We sort a copy so the caller's array is untouched (sort in place to drop that O(n) copy).

Java

public boolean containsDuplicate(int[] nums) {
    int[] a = nums.clone(); // keep the input unchanged
    Arrays.sort(a);
    for (int i = 1; i < a.length; i++) {
        if (a[i] == a[i - 1]) return true; // equal values are now neighbours
    }
    return false;
}

Much faster; sorted in place it needs almost no memory, but sorting does more work than needed.

OptimalHash Set of Seen Values

Time O(n)Space O(n)

Walk the array once, remembering every value in a HashSet. Set.add returns false when the value is already present — that is exactly the moment a duplicate appears.

Java

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

Dry run[4,7,1,7]

i current changed

i=0
4
i
7

1

7

seen={4}
i=1
4

7
i
1

7

seen={4,7}
i=2
4

7

1
i
7

seen={4,7,1}
i=3
4

7

1

7
i
7 seen → true ✔

Linear time with early exit — the standard answer; trades O(n) memory for speed.

Pro tip

Pre-size the set (new HashSet<>(2 * n)) to avoid rehashing on large inputs.

At a glance

Level	Approach	Time	Space
Brute Force	Compare Every Pair	`O(n²)`	`O(1)`
Better	Sort, then Check Neighbours	`O(n log n)`	`O(n) copy (O(log n) in place)`
Optimal	Hash Set of Seen Values	`O(n)`	`O(n)`

Common pitfalls

Starting the inner loop at j = 0 — compares an element with itself.
Sorting the caller's array without saying so — a hidden side effect.
Building the whole set first and comparing sizes — correct, but loses the early exit.

Interview tips

Ask whether the input may be modified — it decides between in-place sort and a copy.
Name the time–space trade-off: sort uses little memory, the set is linear time.
Mention that add() returning false doubles as the lookup.

Pattern

Hash set membership → “have I seen this before?” questions over a single pass.

My notes saved in this browser