Contains Duplicate is the simplest possible use of a hash set. It is the sibling of Two Sum: the same trick of remembering what you have already seen so the next lookup is instant.
Problem. Given an integer array nums, return True if any value appears at least twice, and
False if every element is distinct.
Example: nums = [1, 2, 3, 1] → True (the value 1 appears twice). For nums = [1, 2, 3, 4] → False.
The slow way first
The obvious idea: compare every pair of numbers. For each element, loop over all the others and check for a match. That works, but it is O(n²) — far too slow for a big array.
A faster idea is to sort the array first, then any duplicate would sit next to its twin. That is O(n log n) — better, but it changes the array and still is not the fastest we can do.
The idea: remember what you've seen
Walk the array once. Keep a set of every value seen so far. For each num, ask one question: is num already in the set? If yes, we just found a repeat — return True. If no, add num to the set and keep going. If we reach the end without a hit, everything was distinct — return False.
A set checks membership in O(1), so one pass is enough. We never need to compare two numbers directly — the set does the remembering for us.
Walk through it
Step through the animation. The pointer num scans left to right and the seen set fills up underneath. The first three values (1, 2, 3) are all new, so each gets added. When num reaches the last 1, it is already in the set — that earlier 1 was stored on the very first step — so we stop and return True.
Pseudocode
make an empty set called "seen"
for each value num in nums:
if num is already in seen:
return True # found a duplicate
add num to seen # remember this value
return False # got through everything with no repeatThe Python solution
def contains_duplicate(nums):
seen = set()
for num in nums:
if num in seen:
return True
seen.add(num)
return Falseseenis a set — a collection that answers "is this value in here?" in O(1).- We loop over each
numin the array exactly once. - Line 4 is the O(1) membership test — the heart of the trick.
num in seenchecks a hash, not the whole array. - If the value is new we run
seen.add(num)so a later copy can find it. - If the loop finishes without ever returning
True, every value was distinct, so we returnFalse.
Complexity
| Case | Time | Notes |
|---|---|---|
| Brute force (every pair) | O(n²) (slow) | two nested loops |
| Sort then scan neighbors | O(n log n) (moderate) | the sort dominates |
| Hash set (this solution) | O(n) (moderate) | one pass, O(1) lookups |
O(n) (moderate)We trade O(n) extra space (the set) for the fastest possible time. That same trade — use a hash structure to remember things and look them up instantly — powers Two Sum, anagram checks, and many more.
When this pattern shows up
Any time a problem asks "does this value exist / have I seen this before / are there any repeats," reach for a hash set. Contains Duplicate, Two Sum, and "valid anagram" are all the same move: remember what you've seen so the next lookup is O(1).
Tempting one-liner: return len(set(nums)) != len(nums). It is correct and also O(n), but it always builds
the whole set first. The one-pass version can return as soon as it sees the first repeat, which is
better when a duplicate appears early.
Practice
For nums = [1, 2, 3, 1], at which value do we return True, and why?
1. Why is the hash-set solution O(n) instead of O(n²)?
2. When does the function return True?
3. Why do we add num to the set after the membership check, not before?
4. What is the extra space used by this solution?