Contains Duplicates
Given an integer array numstruefalse
Example 1
Output: true
Explanation: 1 appears twice.
Example 2
Output: false
Explanation: all values are different.
How to Think About It
Step 1: Comparing every pair
Two loops comparing every pair work, but take O(n²).
Step 2: Sorting brings copies together
After sorting, equal values sit next to each other, so one pass comparing neighbours finds a repeat. That is O(n log n) and needs no extra memory if sorting in place is allowed.
Step 3: A set remembers what you have seen
Walk through the array and add each value to a HashSetSet.addfalsetrue
Walkthrough
nums = [1, 2, 3, 1]
| Value | Already in the set? | Set after |
|---|---|---|
| 1 | no | {1} |
| 2 | no | {1, 2} |
| 3 | no | {1, 2, 3} |
| 1 | yes | return true |
Java Solution
The loop stops at the first repeat, so arrays with an early duplicate finish quickly.
import java.util.HashSet;
import java.util.Set;
public class ContainsDuplicates {
public static boolean containsDuplicate(int[] nums) {
Set<Integer> seen = new HashSet<>();
for (int x : nums) {
if (!seen.add(x)) {
return true; // add returns false: x was already there
}
}
return false;
}
public static void main(String[] args) {
System.out.println(containsDuplicate(new int[] {1, 2, 3, 1})); // true
System.out.println(containsDuplicate(new int[] {1, 2, 3, 4})); // false
}
}
The original implementation,
Complexity
- Set: O(n) time, O(n) space.
- Sorting: O(n log n) time, O(1) extra space with an in-place sort.
When the two copies must also be close together, see