Contains Duplicate

Easy · rating 850 · arrays, hashing

The first line contains n. The second line contains n integers. Print YES if any value appears more than once, otherwise NO.

Editorial

Approach

Add each number to a hash set as you go. If a number is already in the set, you've found a duplicate. If you finish the array without a collision, every value was unique.

Alternative

Sorting first makes duplicates adjacent, so a single scan comparing neighbours also works — that's O(n log n) time but O(1) extra space if you may modify the input. The hash-set method trades space for speed.

seen = set()
for x in nums:
    if x in seen: return True
    seen.add(x)
return False

Complexity

Time: O(n). Space: O(n).

Open Contains Duplicate in Code Arena →