Contains Duplicate
A set answers 'have I seen this before?' in O(1).
Duplicate Check
Problem
Given an array of integers, determine whether at least one value appears more than once. Return true as soon as a repeated value is detected; otherwise, return false after examining the entire array.
Examples
Input: [4, 1, 7, 4]
Output: true
Input: [2, 5, 9, 1]
Output: false
The Goal
Return True if any value appears at least twice in nums, and False if every value is different.
For [4, 1, 7, 4], the second 4 is a repeat, so the answer is True.
You don't need counts. For each number, you only need to know whether it came up before.
Ask the set
For each number, ask whether it's already in seen. A hash set answers in constant time on average.
Seen before means a repeat. Not seen means add it and move on.
Key Idea: Remember What Came Before
Keep a set seen of the numbers already read. A set holds each value once and answers value in seen without scanning.
Check before you add. If the check finds the number, it came up earlier and you can stop. If not, add it so later numbers can find it.
A list would work too, but value in a_list scans the list, which makes the loop O(n²).
value in seen asks whether the number came up earlier.
The second 4: yes.
The Algorithm
seen = set()
for value in nums:
if value in seen:
return True
seen.add(value)
return Falselen(set(nums)) < len(nums) gives the same answer in one line. The loop can stop at the first repeat; the one-liner always builds the whole set.
| Approach | Time | Space | How |
|---|---|---|---|
| Hash set | O(n) | O(n) | One lookup per number |
| Sort, then compare neighbors | O(n log n) | O(1) to O(n) | Repeats end up side by side |
| Compare every pair | O(n^2) | O(1) | Rechecks earlier numbers |
Walkthrough
Run it on [4, 1, 7, 4].
4, 1 and 7 are each new: the lookup misses and the number goes into seen. At index 3, the lookup for 4 hits, and the loop returns True there.
Try Break it. With no repeats, every lookup misses, and the answer is False only after the last number.
Checkpoint · predict the next step
Step 4 of 9 on the stage: Is 1 in seen? No: this is the first 1.
i on 1 (index 1) · seen = {4}
Pitfalls
- Create
seenonce, before the loop. Created inside it, the set forgets everything each time. - Don't return
Falseat the first new number. A repeat can still come later. - One number, or none, can't repeat: the answer is
False. - Negative numbers and zero need nothing special. The set compares values.
Why is the set scan faster than comparing every pair?
Complexity
Each number gets one lookup and at most one add, constant time on average, so time is O(n).
The set can end up holding every number, so extra space is O(n). Sorting first uses less memory but costs O(n log n) time.
One pass with a hash set
- Scan the listEach number once.dominantO(n)
- Lookup and addOn average, per number.O(1)
- seenUp to one entry per number.dominantO(n)
| n | 10 | 100 | 1,000 | 10,000 |
|---|---|---|---|---|
| O(n) | 10 | 100 | 1K | 10K |
One pass, paid for with a set.
In short
Add each element to a hash set; if an insert finds the value already present, there's a duplicate. Equivalently, compare the size of a set built from the array to the array length. Sorting also works in O(n log n) but the set is faster and clearer.
Common mistake
Reaching for a nested loop (O(n²)) when a single set pass is both simpler and faster.