Contains Duplicate
Contains Duplicate: return true if any value appears at least twice in nums, and false if every element is distinct.
- 1 <= nums.length <= 10⁵
- -10⁹ <= nums[i] <= 10⁹
Intuition
You only need to know whether a value has been seen before — not where, not how often. A set answers exactly that question in O(1), so walk once and ask on arrival: have I met you already? The first yes ends the scan.
Any question of the form 'has this value appeared before?' is a hash-set question. The moment you catch yourself writing a second loop only to re-scan what you already walked past, replace the inner loop with a set lookup. This same trick powers Two Sum, Longest Consecutive Sequence, and cycle detection in a linked list.
Approach
Before reading on: the brute force compares every pair. Ask what that repeats needlessly, and what you would have to remember so that each element is examined only once. Aim for O(n) time.
Why the brute force is the wrong shape
Comparing every pair with two nested loops is the obvious first idea, and it is correct: for each i, look at every j > i and report a match. But it does ~n²/2 comparisons, and on the 10⁵-element inputs the constraints allow that is around five billion operations. The deeper problem is that it re-derives the same fact repeatedly — after checking nums[0] against the whole tail, it throws that knowledge away and starts over at nums[1]. The fix is to remember what you have already seen.
A set turns 'have I seen this?' into one lookup
A hash set stores values and answers membership in O(1) average time. Walk the array left to right; at each element, first ask whether it is already in the set. If it is, two equal values exist at different indices, which is exactly the definition of a duplicate — return true immediately. If not, add it and move on. Each element is examined once and costs O(1), so the whole scan is O(n) time and O(n) space. The early return matters: on an array that starts [1, 1, ...] you stop after two elements no matter how long the input is.
Sorting is the space-free alternative
If you may modify the input and want O(1) extra space, sort it first. Equal values become neighbours, so a single pass comparing nums[i] with nums[i-1] finds any duplicate. That is O(n log n) time and O(1) auxiliary space — slower asymptotically, but with no hash overhead and better cache behaviour. Choose by which resource is scarce: the set trades memory for speed, the sort trades speed for memory. In an interview, state both and say which you would ship.
Solution & live demo
Common pitfalls
Comparing lengths without understanding it
return len(nums) != len(set(nums))
seen = set()
for num in nums:
if num in seen:
return True
seen.add(num)The one-liner is correct and idiomatic Python, but it always builds the entire set before answering — no early exit — and an interviewer asking this question wants the scan-and-check reasoning, not a language feature.
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)Adding first means the value you just inserted is always found, so this returns true on the very first element of every input. Check membership, then insert.
Using a list instead of a set
seen = [] if num in seen: ...
seen = set() if num in seen: ...
in on a list is a linear scan, so the solution silently degrades to O(n²) — the exact cost the set was introduced to remove. The syntax is identical, which is what makes this easy to miss.
Edge cases
The loop adds one value and never finds a repeat, so the function returns false.
The second element is already in the set, so it returns true after two steps regardless of length.
A hash set stores any integer, so sign plays no part in membership.
No early exit fires, the scan runs the full n steps and still reports true on the last element.