Contains Duplicate
Detect whether any value appears twice in an array, using a hash set to remember what you have seen
Problem Statement
Given an integer array nums, return true if any value appears at least twice, and false if every element is distinct.
Input: nums = [1, 2, 3, 1]
Output: true (1 appears twice)
Input: nums = [1, 2, 3, 4]
Output: false (all distinct)
Input: nums = [1, 1, 1, 3, 3, 4, 3, 2, 4, 2]
Output: trueIntuition
The naive instinct is to compare every element with every other element — O(n²). Two much better ideas exist, and comparing them teaches a lesson you will reuse constantly.
Two ways to make duplicates easy to spot
- Sort first. Duplicates cannot hide once the array is ordered — they end up sitting next to each other. Then a single pass comparing neighbours is enough.
- Remember as you go. Keep a set of everything seen so far. The instant you meet a number already in the set, you are done.
Sorting is O(n log n) time but O(1) extra space. The set is O(n) time but O(n) space. This is the classic time–space trade-off, and the set version is usually the one you want.
Why does sorting work?
Sorting groups equal values together. If 1 appears at positions 0 and 3 in the original array, after sorting both 1s are adjacent. So a duplicate anywhere in the array becomes a duplicate next to each other — and neighbours are cheap to check.
Why the set is better
The set version can exit early. If the duplicate sits at positions 0 and 1 of a million-element array, the set returns after two steps. Sorting always pays the full O(n log n) before it can answer anything.
empty
Approach
Create an empty set
A set stores only whether a value is present — no counts, no positions. That is exactly the question being asked.
For each number, ask before adding
If the number is already in the set, a duplicate exists → return true right away.
Otherwise add it and continue
If the loop finishes without a hit, every value was distinct → return false.
Solution
def contains_duplicate(nums: list[int]) -> bool:
"""Return True if any value in nums appears more than once."""
seen: set[int] = set()
for num in nums:
if num in seen:
return True # early exit — no need to scan the rest
seen.add(num)
return FalseA one-liner using the same idea — a set drops duplicates, so a shorter set means duplicates existed:
def contains_duplicate(nums: list[int]) -> bool:
return len(set(nums)) < len(nums)The one-liner is elegant but always processes the entire array; the loop can stop early.
The sorting alternative
Worth knowing for when you are told you may not use extra memory:
def contains_duplicate_sorted(nums: list[int]) -> bool:
nums.sort() # mutates the input — O(n log n)
for i in range(len(nums) - 1):
if nums[i] == nums[i + 1]:
return True
return FalseA classic JavaScript trap
[10, 9, 1].sort() returns [1, 10, 9], not [1, 9, 10]. JavaScript's default sort converts elements to strings and compares them alphabetically. Numeric sorts must pass (a, b) => a - b.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(n)
- Time — one pass, with
O(1)average-case set operations. - Space — the set can grow to hold all
nvalues when there are no duplicates.
The sorting version trades this around: O(n log n) time, O(1) extra space (ignoring the sort's internal stack).
Edge Cases
Related Problems
- Two Sum — the same "have I seen it?" idea, but storing indices in a map
- Valid Anagram — counting occurrences instead of just presence
- Number of Good Pairs — counting how many duplicate pairs exist