Contains Duplicate
Say whether any number appears more than once in an array.
- Hash set membership
Before this, know: Arrays and indexes, Hash sets (Set in JavaScript, set in Python)
You get a list of numbers called nums. Answer one yes/no question: does any
number appear more than once? Return true if some value shows up at least
twice, and false if every value is different.
A list is stored as an array: a row of boxes, each with a position number called its index. Indexes start at 0, so the first box is index 0.
Here is a small example, nums = [1, 2, 3, 1]:
- 10
- 21
- 32
- 13
And nums = [1, 2, 3, 4] has no repeats, so the answer is false.
The rules that matter:
- We compare values, not positions. Two different boxes holding the same number count as a duplicate.
- One repeat is enough. We don’t need to count how many, or say which.
- On LeetCode the array has at least 1 number and up to 100,000 of them, and the numbers can be negative.
The notebook in that story is a hash set: a collection that remembers values
and can answer “is this value in here?” in about one step, no matter how many
values it holds. In JavaScript it’s a Set; in Python it’s a set.
look up 1: found
- 1
- 2
- 3
Pause and think
At index 2. After index 0 the notebook holds {4}, after index 1 it holds
{4, 9}. At index 2 we ask “is 4 in the notebook?” and the answer is yes. We
stop right there and return true.
Brute force means trying every possibility. Here that means comparing every
number with every number that comes after it. We use two pointers (variables
that remember a position): i for the first number and j for the second.
Brute force: compare every pair
nums = [1, 2, 3, 1]
- 10
- 21
- 32
- 13
- comparisons so far
- 0
- answer
- —
- First number (i)
- Second number (j)
- Equal pair
Pick nums[0] = 1. Compare it with every number after it.
Which line is running?
function containsDuplicate(nums) {Running now: for (let i = 0; i < nums.length; i++) { for (let j = i + 1; j < nums.length; j++) { if (nums[i] === nums[j]) { return true; } } } return false;}Brute force
function containsDuplicate(nums) { for (let i = 0; i < nums.length; i++) { for (let j = i + 1; j < nums.length; j++) { if (nums[i] === nums[j]) { return true; } } } return false;}def contains_duplicate(nums): for i in range(len(nums)): for j in range(i + 1, len(nums)): if nums[i] == nums[j]: return True return Falsej starts at i + 1, so we never compare a number with itself and never
compare the same pair twice.
Count the comparisons when there are no duplicates (the worst case, because we can’t stop early). With 4 numbers: 3 + 2 + 1 = 6 comparisons.
With 100,000 numbers (LeetCode’s limit): 99,999 + 99,998 + … + 1, which is about 100,000 × 100,000 ÷ 2 = 5,000,000,000 comparisons. Five billion! That takes far too long.
We describe this kind of growth with Big-O notation, a short way of saying how the work grows as the input grows. Work that grows like n × n is O(n²): double the input and the work goes up four times.
If we sort the numbers, equal numbers end up side by side. Then one walk that compares each number with its left neighbour finds any duplicate.
Sort, then compare neighbours
function containsDuplicate(nums) { const sorted = [...nums].sort((a, b) => a - b); for (let i = 1; i < sorted.length; i++) { if (sorted[i] === sorted[i - 1]) { return true; // equal numbers end up side by side } } return false;}def contains_duplicate(nums): s = sorted(nums) for i in range(1, len(s)): if s[i] == s[i - 1]: return True # equal numbers end up side by side return FalseSorting costs about n × log n steps, written O(n log n). That’s much better than O(n²): for 100,000 numbers it’s roughly 1.7 million steps instead of 5 billion. (Log n is “how many times you can halve n before reaching 1”; for 100,000 that’s about 17.) But we can do better still, with no sorting at all.
The brute force spends all its time searching: for each number, “is there another copy anywhere?”. A hash set turns that search into a single question with an instant answer.
Pattern
Hash set: have I seen this?
Use it when: you need to know whether a value has appeared before: duplicates, repeats, 'already visited'.
Signal words
- “contains duplicate”
- “appears twice”
- “any repeated”
- “all unique”
- “first repeated”
- Create an empty hash set called
seen. - Walk through
numsone number at a time. Call the current numbernum. - Ask: is
numalready inseen? If yes, returntrueimmediately. - If not, add
numtoseenand move on. - If the loop ends, nothing repeated. Return
false.
Press Play, or click the player and use the arrow keys. Watch the set grow underneath the array, and watch the code panel: the highlighted line is the one running at that moment. Try the edge cases too: a single number, and negatives.
One pass with a hash set
nums = [1, 2, 3, 1]
- 10
- 21
- 32
- 13
- empty
- num
- —
- answer
- —
- Looking at now
- Already in the set
- Seen before (duplicate)
- Not seen yet
- Just added to the set
Start with an empty hash set called "seen". It will remember every number we walk past, and it can answer "have I seen this?" in about one step.
Which line is running?
function containsDuplicate(nums) {Running now: const seen = new Set(); // every number we have passed so far for (const num of nums) { if (seen.has(num)) { return true; } seen.add(num); } return false;}Notice that in “Example 1” we stop at index 3 and never need to finish the
loop. In “No duplicates” we have to look at every number before we can be sure
the answer is false.
One pass with a hash set
function containsDuplicate(nums) { const seen = new Set(); // every number we have passed so far for (const num of nums) { if (seen.has(num)) { return true; } seen.add(num); } return false;}def contains_duplicate(nums): seen = set() # every number we have passed so far for num in nums: if num in seen: return True seen.add(num) return FalseThe two versions line up until line 5; JavaScript then has a closing brace }
on line 6, so its later line numbers run one ahead of Python’s.
- Line 1: define the function. (On LeetCode, JavaScript uses
var containsDuplicate = function(nums)and Python wraps it inclass Solutionasdef containsDuplicate(self, nums). The body is the same.) - Line 2: create an empty set.
new Set()in JavaScript,set()in Python. Careful: in Python{}makes an empty dict, not an empty set. - Line 3: loop over the values directly.
for (const num of nums)/for num in numshands us each number in turn; we don’t need the index here. - Line 4: the key question.
seen.has(num)/num in seentakes about one step, however big the set is. This is the line that makes the solution fast. - Line 5: if we’ve seen it, we’ve found a duplicate. Return
truestraight away. - Line 7 (JS) / line 6 (Python): otherwise remember the number. Adding to a set also takes about one step. Adding a value that’s already there would do nothing, but we never get that far, because line 4 catches it first.
- Line 9 (JS) / line 7 (Python): the loop finished without a repeat, so
every number is different. Return
false.
Let’s trace nums = [1, 2, 3, 1] by hand. Each row is one trip around the loop.
| index | num | num in seen? | what happens | seen afterwards |
|---|---|---|---|---|
| 0 | 1 | no (empty) | add 1 | {1} |
| 1 | 2 | no | add 2 | {1, 2} |
| 2 | 3 | no | add 3 | {1, 2, 3} |
| 3 | 1 | yes | return true | (we stop here) |
The index 3 row is the moment the notebook pays off: one lookup tells us that 1 has been seen before, without comparing it against 2 and 3 at all.
Brute force
Time
O(n²)
Every number is compared with every number after it: about n × n ÷ 2 comparisons.
Space
O(1)
Only the two pointers i and j. O(1) means 'a fixed amount, however long the input'.
Sort first
Time
O(n log n)
Sorting dominates. The neighbour walk afterwards is just n steps.
Space
O(n)
We sort a copy so we don't change the caller's array. (Sorting in place can bring this down, but it changes the input.)
One pass with a hash set
Time
O(n)
We look at each number once, and each set lookup or insert takes about one step. 100,000 numbers ≈ 100,000 steps.
Space
O(n)
With no duplicates, the set ends up holding every number.
As in Two Sum, we trade memory for time: the set costs extra space, and in return the work grows in a straight line with the input instead of as a square.
What to say out loud, in this order:
- Restate: “Return true if any value appears at least twice.”
- Brute force: “Compare every pair: O(n²) time, O(1) space.”
- Better: “Sort, then compare neighbours: O(n log n).”
- Best: “A hash set gives O(1) lookups, so one pass is O(n) time, O(n) space.”
- Trace a short example, like the dry run above.
Likely follow-up questions:
- “What if you can’t use extra memory?” Sort in place and compare neighbours: O(n log n) time, O(1) extra space.
- “What if duplicates only count within distance k?” That’s Contains Duplicate II: keep a set of only the last k numbers (a sliding window, week 2).
- “Return the duplicate value?” Return
numinstead oftrue.
Related problems:
- Valid Anagram (this week): the next step up, counting how many times each value appears instead of just “seen or not”.
- Two Sum (this week): a hash map that remembers what we’ve seen and where.
- Longest Consecutive Sequence (this week): uses a hash set for instant “is x here?” questions.