Contains Duplicate
You get an array of integers nums. Return true if some value appears in it at least twice, and false if every value is different.
Function
- numsinteger-array
- the integers to check
- Returnsboolean
- true if some value appears at least twice, false otherwise
Constraints
1 ≤ nums.length ≤ 104-109 ≤ nums[i] ≤ 109
Examples
- Input
- nums = [3, 1, 4, 1, 5]
- Output
- true
- Explanation
- The value
1appears at index 1 and again at index 3, so the answer istrue.
- Input
- nums = [2, 7, 1, 8]
- Output
- false
- Explanation
2,7,1and8are four different values, so nothing repeats.
- Input
- nums = [-4, 4, 0]
- Output
- false
- Explanation
-4and4have the same absolute value but are different numbers, and0appears once, so the answer isfalse.
+17 hidden tests on Submit
Follow-up
Can you stop as soon as you meet the first repeated value, instead of always reading the whole array?
Hints
Open them one at a time. Each one gives away a little more.
Comparing every value with every other value works, but for
10^4values that is about5 × 10^7comparisons. What could you remember about the values you have already passed?A repeat means the current value is one you have met before. A hash set answers "have I met this value?" in constant time on average.
Walk the array once with an empty set. For each value, return
trueif it is already in the set; otherwise add it. If the loop ends, every value was different.
Solution
A repeat is a value you have met before, and the work is in answering "have I met this?" quickly. Comparing every pair answers it, but for n = 10^4 that is n(n-1)/2, about 5 × 10^7 comparisons. Sorting brings equal values next to each other, and a hash set answers the question in O(1) on average, which gives a single pass.
Sort, then compare neighbours
Intuition
In a sorted array, equal values sit next to each other. [3, 1, 4, 1, 5] sorts to [1, 1, 3, 4, 5], and the two 1s now touch. So after sorting you only compare each value with the one right before it: n-1 comparisons instead of the n(n-1)/2 it takes to try every pair.
If no two neighbours are equal, no two values anywhere are equal: any value between two copies of x in sorted order would have to be both at least x and at most x, so it would be another x.
The sort dominates at O(n log n) time. Sorting nums in place needs no extra array, but it reorders the caller's input; if that is not allowed, sort a copy, which costs O(n) space.
Algorithm
- Sort
numsin increasing order. - Loop
ifrom 1 to the last index. - If
nums[i]equalsnums[i-1], returntrue. - After the loop, return
false.
def containsDuplicate(nums):
nums.sort()
# After sorting, equal values sit next to each other.
for i in range(1, len(nums)):
if nums[i] == nums[i - 1]:
return True
return FalseOne pass with a hash set
Intuition
Walk the array once and keep every value you have passed in a hash set. Before adding a value, ask the set whether it is already there. For [3, 1, 4, 1, 5] the set grows to {3, 1, 4}, and when the second 1 arrives the set already holds it, so you return true without reading the 5.
The set always holds exactly the values before the current position, so a hit means the current value appeared earlier, and reaching the end without a hit means all values are different.
A hash set lookup and insert take O(1) time on average, so the whole pass is O(n). The price is memory: with no repeat, the set ends up holding all n values.
Algorithm
- Create an empty hash set
seen. - For each value in
nums, if it is inseen, returntrue. - Otherwise add it to
seen. - After the loop, return
false.
def containsDuplicate(nums):
seen = set()
for num in nums:
if num in seen:
return True
seen.add(num)
return False
Pitfalls and edge cases
The logic is short, so the bugs are in loop bounds and in what you compare.
- Comparing every pair with the inner loop starting at
j = i. Every value then matches itself and the answer is alwaystrue. - Comparing neighbours without sorting first. In
[9, 1, 2, 3, 9]the two9s are not next to each other. - Starting the neighbour loop at index 0 and reading
nums[-1]. Start at 1, and an array of one value correctly returnsfalse. - Treating values with the same absolute value as equal, for example by hashing
abs(x).-4and4are different numbers. - Writing a C sort comparator that returns
x - y. Here the difference stays within±2 × 10^9, below theintlimit of2^31-1 = 2147483647, so it happens to fit; with values near theintlimits it overflows and the sort comes out wrong. Return(x > y) - (x < y)instead.
Frequently asked questions4
What is the time complexity of Contains Duplicate?
The hash set solution runs in O(n) time on average and uses O(n) extra space. Sorting first takes O(n log n) time and no extra array if you may reorder the input. Comparing every pair takes O(n²) time.
Can you solve Contains Duplicate without extra space?
Yes, if you are allowed to reorder the array: sort it in place and compare each value with its neighbour. That trades the O(n) set for O(n log n) time. Without reordering and without extra memory, the only option left is the O(n²) pair check.
Why does a hash set make the check fast?
A hash set stores values by their hash, so asking whether it holds a value takes constant time on average instead of a scan. Each element costs one lookup and one insert, which makes the whole pass linear.
Is comparing the set size with the array length a valid solution?
Yes. Building a set from all of nums and checking whether it is smaller than the array gives the right answer in O(n) time. The loop version is often better because it returns as soon as it meets the first repeat, while building the whole set always reads every value.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
Python
def containsDuplicate(nums):
# Write code hereCase 1
Case 2
Case 3
Input
nums = [3, 1, 4, 1, 5]
Expected
true