Contains Duplicate
Contains Duplicate is LeetCode 217 (Easy). Given an integer array nums, return true if any value appears at least twice, and false if every element is distinct.
- Values go from -10⁹ to 10⁹, so they cannot be used as indexes into a counting array.
- With up to 10⁵ elements, comparing every pair (about 5 · 10⁹ checks) is too slow; the target is one pass.
- 1 <= nums.length <= 10⁵
- -10⁹ <= nums[i] <= 10⁹
Intuition
The brute force compares every pair, re-checking the same earlier values again and again. But the only fact it needs about the past is which values have appeared, not where or how often.
A hash set stores exactly that and answers "have I seen this?" in O(1) on average. So the solution walks the array once and asks that one question for each value. The first "yes" is the answer.
Any "has this value appeared before?" question is a hash-set question: as soon as an inner loop only re-scans elements already walked past, replace it with a set lookup. The same move powers Two Sum (a map from value to index) and Longest Consecutive Sequence. When the repeat must also be close by, as in Contains Duplicate II, the set becomes a sliding window.
Approach
Before reading on: the brute force compares every pair. What does it keep re-checking, and what is the least you would need to remember so each element is looked at only once? Trace [1, 2, 3, 1] with that memory.
Two ways to solve it
Walk once, check each value against a set of the ones already seen, and stop at the first repeat.
- Speed: one O(1) lookup per element.
- Memory: a set of up to n values.
- Early exit: a repeat near the front ends it at once.
The standard answer.
Sort the array so equal values become neighbours, then scan once for two equal neighbours.
- Speed: the sort dominates.
- Memory: no set; the sort reorders
numsin place. - Catch: it changes the input.
Useful when extra memory is not allowed.
The hash set is faster and leaves the input untouched, so the steps, code and live demo below follow it. The sorting code comes after the demo.
Start with an empty set
seen = set() will hold every value already walked past. A set answers membership in O(1) on average, so one lookup replaces the brute force's inner loop.
Check each value, then add it
For each num, first ask whether it is in seen. If it is, an earlier index holds the same value, so return true straight away; nothing later can change the answer. Otherwise add num so that any later copy will find it.
Return false after the loop
Reaching the end means every lookup missed, so all n values are distinct. Each element cost one lookup and at most one insert, giving O(n) time and O(n) space for the set.
Contains Duplicate solution in Python | C++ | Java
Sorting version
Sorting puts equal values next to each other, so a single pass comparing each element with the one before it finds any duplicate.
Common pitfalls
Adding before checking
for num in nums:
seen.add(num)
if num in seen:
return Truefor num in nums:
if num in seen:
return True
seen.add(num)The value just inserted is always found, so this returns true on the first element of every input, including [1, 2, 3, 4].
Using a list instead of a set
seen = [] if num in seen: ...
seen = set() if num in seen: ...
in on a list scans it element by element, so the solution quietly becomes O(n²) and times out on 10⁵ distinct values. The syntax is the same, which is why it is easy to miss.
Complexity
Contains Duplicate I, II and III
The three problems share a name but ask different questions, so the data structure changes.
| Problem | Asks | Tool |
|---|---|---|
| 217 Contains Duplicate (this page) | any value twice, anywhere | hash set of all values |
| 219 Contains Duplicate II | equal values at most k indices apart | set of the last k values (sliding window) |
| 220 Contains Duplicate III | values within t of each other, at most k apart | buckets of width t + 1, or an ordered set |
Contains Duplicate FAQ
Is len(set(nums)) != len(nums) a good Python answer?
Yes, it is correct and accepted on LeetCode. It always builds the full set before answering, so it cannot stop early on an input like [1, 1, ...], and an interviewer will usually ask you to explain the loop it hides, which is the solution on this page.
Why use a hash set and not a hash map?
Only the presence of a value matters, not a count or an index, so the set stores less. A map from value to count also works but does extra bookkeeping the answer never uses.