Contains Duplicate
Check whether any value appears more than once in an array. Compare the brute force, sorting and hash set solutions and their complexity.
Updated Quick read: 3 min read
Approaches at a glance
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n²) | O(1) |
| Sort, then compare neighbours | O(n log n) | O(n) |
| Hash set | O(n) | O(n) |
The problem
Given an array of integers, return true if any value appears at least twice, and false if every value is different.
[1, 2, 3, 1] → true (1 appears twice)
[1, 2, 3, 4] → false
[] → falseApproach 1: brute force
Compare every element with every later element.
JavaScript
function containsDuplicateBruteForce(numbers) {
for (let i = 0; i < numbers.length; i++) {
for (let j = i + 1; j < numbers.length; j++) {
if (numbers[i] === numbers[j]) return true;
}
}
return false;
}Python
def contains_duplicate_brute_force(numbers):
for i in range(len(numbers)):
for j in range(i + 1, len(numbers)):
if numbers[i] == numbers[j]:
return True
return FalseTime O(n²). Space O(1).
Approach 2: sort, then compare neighbours
After sorting, equal values sit next to each other, so one pass comparing each element with the previous one is enough.
JavaScript
function containsDuplicateSorted(numbers) {
const sorted = [...numbers].sort((a, b) => a - b);
for (let i = 1; i < sorted.length; i++) {
if (sorted[i] === sorted[i - 1]) return true;
}
return false;
}Python
def contains_duplicate_sorted(numbers):
ordered = sorted(numbers)
for i in range(1, len(ordered)):
if ordered[i] == ordered[i - 1]:
return True
return FalseThe copy [...numbers] keeps the caller's array unchanged, since sort reorders the array it is called on.
Time O(n log n) for the sort. Space O(n) for the copy.
Approach 3: hash set
Keep a set of the values seen so far. A value that is already in the set is a duplicate.
JavaScript
function containsDuplicate(numbers) {
const seen = new Set();
for (const value of numbers) {
if (seen.has(value)) return true;
seen.add(value);
}
return false;
}Python
def contains_duplicate(numbers):
seen = set()
for value in numbers:
if value in seen:
return True
seen.add(value)
return FalseThis returns as soon as the first duplicate is found, without looking at the rest of the array.
Time O(n). Space O(n).
A shorter version, and its cost
JavaScript
function containsDuplicateShort(numbers) {
return new Set(numbers).size !== numbers.length;
}Python
def contains_duplicate_short(numbers):
return len(set(numbers)) != len(numbers)A set drops repeated values, so it ends up smaller than the array when there is a duplicate. This has the same O(n) time and space, but it always processes the whole array, even when the first two elements are equal.
Which to choose
The hash set is the usual answer: it is the fastest. Sorting is worth mentioning when memory matters more than time and you are allowed to reorder the input in place, since that avoids the extra set.
Try it yourself
Copy a solution from above, add the lines below, and run it. For JavaScript, paste both into the browser console, or save them in a file and run it with node. For Python, save them in a file and run it with python.
JavaScript
console.log(containsDuplicate([1, 2, 3, 1])); // true
console.log(containsDuplicate([1, 2, 3, 4])); // falsePython
print(contains_duplicate([1, 2, 3, 1])) # True
print(contains_duplicate([1, 2, 3, 4])) # FalseThe comment after each line is the result you should see.
Common mistakes
- Using an array for
seen.seen.includes(value)is a loop, which makes the solution O(n²) again. - Calling
sort()with no comparison function. Numbers are then compared as text. Equal numbers still end up adjacent, so the answer happens to be right here, but the habit causes bugs elsewhere.
Original problem: LeetCode 217: Contains Duplicate