Problem. Return True if any value appears at least twice in nums, otherwise False.
[1, 2, 3, 1] → True
[1, 2, 3, 4] → False
ML context. Duplicate detection is a data-quality step in every pipeline: the same example in the training and test sets leaks the answer and inflates your metrics. Deduplicating user ids, image hashes or document fingerprints is this problem at scale, and its variants (duplicates within a time window, near-duplicates within a tolerance) are the ones you'll meet in practice.
1. Step 1: Clarify
| Question | Answer | Why it matters |
|---|---|---|
| n? | Up to 10⁵ | O(n²) = 10¹⁰: too slow |
| Values? | Any integers (−10⁹ to 10⁹) | Too wide for a plain boolean array |
| Extra memory allowed? | Yes (ask!) | Decides set versus sort |
| Can I modify the input? | Maybe | Sorting in place needs it |
| Return early? | Yes, at the first repeat | Best case becomes O(1) |
2. Step 2: Brute force: compare every pair
def contains_duplicate_brute(nums):
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] == nums[j]:
return True
return False
assert contains_duplicate_brute([1, 2, 3, 1])
assert not contains_duplicate_brute([1, 2, 3, 4])
assert not contains_duplicate_brute([])
print("brute force works: O(n²) time, O(1) space")
O(n²) time, O(1) space. At n = 10⁵: about 5 × 10⁹ comparisons. Too slow.
3. Step 3: Optimise
The waste: each new value is compared against every earlier value one at a time. Two ways to fix it: bring equal values together (sorting), or remember the earlier values in a structure with O(1) lookup (hashing).
Optimisation A: sort, then compare neighbours
After sorting, equal values sit next to each other, so one pass over adjacent pairs finds any duplicate.
def contains_duplicate_sort(nums):
nums = sorted(nums) # O(n log n); sort in place if allowed
return any(nums[i] == nums[i + 1] for i in range(len(nums) - 1))
assert contains_duplicate_sort([1, 2, 3, 1])
assert not contains_duplicate_sort([1, 2, 3, 4])
print("sort version: O(n log n) time, O(1) extra if sorted in place")
O(n log n) time; O(1) extra memory if you may sort in place (nums.sort()), otherwise O(n) for the copy.
Optimisation B: one pass with a hash set
Keep a set of values seen so far. For each value: if it's already in the set, we found a duplicate; otherwise add it.
import random
def contains_duplicate(nums):
seen = set()
for x in nums:
if x in seen: # O(1) average
return True # stop at the first repeat
seen.add(x)
return False
def brute(nums):
return any(nums[i] == nums[j] for i in range(len(nums)) for j in range(i + 1, len(nums)))
rng = random.Random(36)
for _ in range(1000):
nums = [rng.randint(-20, 20) for _ in range(rng.randint(0, 12))]
assert contains_duplicate(nums) == brute(nums)
assert len(set([1, 2, 3, 1])) < 4 # the one-liner: correct, but never stops early
print("hash set: O(n) time, O(n) space, matches brute force on 1,000 cases")
- Time: O(n) average, and it stops early at the first repeat.
- Space: O(n) for the set.
- The one-liner
len(set(nums)) < len(nums)is also O(n), but always builds the whole set. On a stream with an early duplicate, the loop wins.
Quick check
Sorting uses O(1) extra memory and hashing uses O(n). When is sorting the better choice?
Show the answer
B. When memory is the binding constraint and you may modify the input: O(n log n) time but no extra set — It's a time-for-memory trade: the hash set is faster but needs O(n) extra memory.
4. When the constraints change
Change A: duplicates only count within k positions
"Is there i ≠ j with nums[i] == nums[j] and |i − j| ≤ k?" Keep a set of only the last k values: add each
new value, and remove the one that falls out of the window. O(n) time, O(k) space.
import random
def duplicate_within_k(nums, k):
window = set()
for i, x in enumerate(nums):
if x in window:
return True
window.add(x)
if len(window) > k:
window.remove(nums[i - k]) # value now more than k positions back
return False
def brute_k(nums, k):
return any(nums[i] == nums[j] for i in range(len(nums)) for j in range(i + 1, min(len(nums), i + k + 1)))
assert duplicate_within_k([1, 2, 3, 1], 3)
assert not duplicate_within_k([1, 2, 3, 1, 2, 3], 2)
rng = random.Random(37)
for _ in range(1000):
nums = [rng.randint(0, 6) for _ in range(rng.randint(0, 12))]
k = rng.randint(0, 5)
assert duplicate_within_k(nums, k) == brute_k(nums, k)
print("sliding-window set: O(n) time, O(k) space")
ML version: "has this user sent the same request in the last 1,000 events?"
Change B: near-duplicates (values within t of each other, within k positions)
Exact hashing can't find "close" values. Bucket by value: put x in bucket x // (t + 1). Two values within t
are either in the same bucket or in neighbouring ones, so check three buckets. Still O(n) time, O(k) space.
import random
def near_duplicate(nums, k, t):
width = t + 1
buckets = {}
for i, x in enumerate(nums):
b = x // width
if b in buckets:
return True # same bucket ⇒ within t
for nb in (b - 1, b + 1):
if nb in buckets and abs(x - buckets[nb]) <= t:
return True
buckets[b] = x
if i >= k:
del buckets[nums[i - k] // width] # keep only the last k values
return False
def brute_near(nums, k, t):
return any(abs(nums[i] - nums[j]) <= t
for i in range(len(nums)) for j in range(i + 1, min(len(nums), i + k + 1)))
rng = random.Random(38)
for _ in range(1000):
nums = [rng.randint(-30, 30) for _ in range(rng.randint(0, 12))]
k, t = rng.randint(1, 5), rng.randint(0, 6)
assert near_duplicate(nums, k, t) == brute_near(nums, k, t)
print("bucketing finds near-duplicates in O(n)")
Bucketing by a quantised value is the same idea as locality-sensitive hashing, used to find near-duplicate documents and images: similar items are hashed to the same bucket on purpose.
Change C: small integer range, or billions of items
- Values in 0..R with small R: a boolean array (or a bit array) replaces the set: O(n + R) time, R bits, no hashing.
- Billions of items: a set of 10⁹ ids needs tens of gigabytes. A Bloom filter answers "definitely new" or "probably seen" with about 10 bits per item and a tunable false-positive rate. Data pipelines use one to skip most exact checks.
The full table
| If the constraint becomes… | Best approach | Time | Space |
|---|---|---|---|
| O(1) extra memory, may sort | Sort, compare neighbours | O(n log n) | O(1) |
| Classic | Hash set, stop early | O(n) | O(n) |
| Values in a small range R | Boolean / bit array | O(n + R) | O(R) |
| Within k positions | Sliding-window set | O(n) | O(k) |
| Within value t and k positions | Buckets of width t + 1 | O(n) | O(k) |
| Billions of items | Bloom filter (+ exact check on "maybe") | O(n) | ~10 bits per item |
| Near-duplicate documents / images | Locality-sensitive hashing | ~O(n) | O(n) signatures |
Quick check
Why does bucketing by x // (t + 1) find values within t of each other with only three bucket checks?
Show the answer
A. Two values within t can't be more than one bucket apart, so checking the value's own bucket and its two neighbours covers every possible match — Bucket width t + 1 guarantees close values land in the same or an adjacent bucket.
5. Saying it out loud
"Comparing every pair is O(n²). Sorting brings equal values together: O(n log n) with O(1) extra if I can sort in place. With memory available, I'd keep a set of seen values and return at the first repeat: O(n) time, O(n) space. If duplicates only count within k positions, the set holds just the last k values; for near-duplicates I'd bucket by value."
Check yourself
- What's the waste in the brute force, and what are the two ways to remove it?
- Compare the sort and set versions in time and memory.
- Why can the loop beat
len(set(nums)) < len(nums)? - How does the window version keep memory at O(k)?
- Why do near-duplicates need three bucket checks?
- What would you use for a billion ids, and what does it give up?
Answers
- Each value is compared against all earlier ones individually; fix it by sorting (equal values adjacent) or by a set (O(1) membership).
- Sort: O(n log n) time, O(1) extra if in place. Set: O(n) time, O(n) extra.
- It stops at the first repeat; the one-liner always processes everything.
- It removes the value k positions back each step, so the set never holds more than k values.
- Values within t are in the same bucket or an adjacent one (width t + 1).
- A Bloom filter: ~10 bits per id, but it can say "probably seen" for a new id (false positives), so confirm those exactly if needed.