Interview challenge · easy · array, hash-set
Contains Duplicate
The challenge
Given an integer array nums, return true if any value appears at least twice, and false if every element is distinct.
Example
[1, 2, 3, 1] -> true
[1, 2, 3, 4] -> false
[1, 1, 1, 3, 3, 4, 3, 2, 4, 2] -> trueIdea: remember what you have seen in a hash set; the first number already in the set is a duplicate. Time O(n), space O(n). In C, sorting first and comparing neighbours gives O(n log n) with no extra memory.
The solution
# Contains Duplicate - ayotl.dev
def contains_duplicate(nums):
seen = set() # O(1) lookups
for n in nums:
if n in seen:
return True # seen it before
seen.add(n)
return False
print(contains_duplicate([1, 2, 3, 1]))
print(contains_duplicate([1, 2, 3, 4]))
$ python3 contains_duplicate.py
True
False