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.
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, so the work is in answering "have I met this?" quickly. Comparing every pair takes about 5 × 10^7 comparisons for n = 10^4. Sorting puts 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 touch. So after sorting you compare each value only with the one before it, n-1 comparisons.
If no two neighbours are equal, no two values anywhere are: any value between two copies of x in sorted order would 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 in place needs no extra array but reorders the caller's input; sorting a copy 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. 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. For [3, 1, 4, 1, 5] the set holds {3, 1, 4} when the second 1 arrives.
Lookup and insert take O(1) time on average, so the pass is O(n). 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
- Starting the inner loop of a pair check 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.
Frequently asked questions3
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 may reorder the array: sort it in place and compare each value with its neighbour, trading 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.
Is comparing the set size with the array length a valid solution?
Yes. Build a set from all of nums and check whether it is smaller than the array. It runs in O(n) time and O(n) space.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
def containsDuplicate(nums):
# Write code hereTest #1
Test #2
Test #3
Argument
nums = [3, 1, 4, 1, 5]
Expected Output
true