The problem
You are given a list of numbers. Return true if any number appears at least twice, and false if every number is different.
Input: nums = [3, 8, 1, 5, 8, 2] Output: true (8 appears twice)
Picture it
Imagine a stamp collector tipping an envelope of stamps into an album, one at a time. Before sticking each stamp in, they glance at the album: “do I already have this one?” In the picture, each stamp is one number from the list and the album is a set: a box that remembers what it has seen and can answer “seen it?” instantly. The moment a stamp is already in the album, we have found a duplicate and can stop.
How to recognise it
- The question is a plain yes/no about repeats: "does any value appear twice?"
- You do not need positions or counts, only whether you have seen this value before.
- One repeat is enough to answer, so you can stop early.
- The list is not sorted, and n can be up to 10^5, which rules out comparing every pair.
- "Have I seen this before?" is the textbook question a set answers in O(1).
Start with brute force
Compare every pair of positions (i, j) with i < j. If two hold the same number, there is a duplicate.
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
There are n(n − 1)/2 pairs, so time is O(n²) and extra space is O(1). LeetCode allows n up to 10^5, which is about 5 × 10^9 comparisons when every number is different: far too slow.
A middle step is to sort first, then compare neighbours: O(n log n) time. It works, but it either changes the input or copies it, and it still does more work than needed.
From brute force to the idea
- Find the waste. For each number, the inner loop scans the rest of the list to answer one question: "is there another copy of this value?"
- Ask the question the other way round. Instead of looking ahead for a copy, look back: "have I already passed this value?" A copy is always found when its second occurrence arrives.
- Remember what you have passed. A set holds the values seen so far and answers
x in albumin O(1) on average. - Check, then add. For each x, if it is already in the set, return
True. Otherwise add it and move on. - Finish the loop. If no value was ever found in the set, every number was different, so return
False.
This is the key idea: one pass with a set of values seen so far, stopping at the first repeat.
The key idea
A set answers “have I seen this before?” in one step, so one pass over the list is enough: O(n) time instead of comparing every pair.
Python solution
def contains_duplicate(nums):
album = set()
for x in nums:
if x in album:
return True
album.add(x)
return FalseIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n²): every pair is compared once | O(1): only two loop indices |
| Set of seen values (shown code) | O(n): one pass, each lookup and insert is O(1) on average | O(n): if all numbers differ, every one is stored |
Edge cases
- Empty list: the loop never runs, so it returns
False. - One number: returns
False; nothing can repeat. - Repeat at the very start (
[5, 5, 1, 2, 3]): returnsTrueafter reading only two numbers. The early return matters on huge inputs. - Negatives and zero (
[-1, 0, 1, -1]): returnsTrue; a set hashes any integer. - All different: the worst case for memory, as the set ends up holding n values.
- One-liner alternative:
len(set(nums)) != len(nums)gives the same answers, but always builds the whole set, even when the repeat is at position 1.
Common mistakes
- Adding x to the set before checking it. Then every value finds itself, and
[1, 2, 3]returnsTrue. - Using a list instead of a set for
album.x in listscans the list, which quietly brings back O(n²). - Sorting and then comparing
nums[i]withnums[i + 2]or other non-neighbours. After sorting, equal values are always adjacent, so neighbours are enough.
Return True if some value appears twice at positions i and j with j − i ≤ k. For [1, 2, 3, 1] with k = 3 the answer is True; for [1, 2, 3, 1, 2, 3] with k = 2 it is False. Describe your approach, then write it if you like.
Compare with our answer
A set no longer says enough: you also need to know where you last saw each value. Store value → last position in a dictionary. When x arrives, check whether its last position is within k, then overwrite it with the current position, because the most recent copy is always the closest one for anything still to come.
def contains_nearby_duplicate(nums, k):
last = {} # value -> most recent position
for i, x in enumerate(nums):
if x in last and i - last[x] <= k:
return True
last[x] = i
return False
[1, 0, 1, 1] with k = 1 returns True (the last two 1s). Time O(n), space O(n). (A set that only holds the last k values also works and caps the space at O(k).)
A strong answer mentions: storing positions instead of just values, updating to the most recent position, and why the closest earlier copy is the only one worth checking.
1. You must report the first value that appears for a second time when reading a list left to right. Which approach fits best?
The set version returns exactly the value whose second copy comes first. Sorting loses the reading order, and counting returns a repeated value but not necessarily the one whose repeat arrives first.
2. Why does the shown solution run in O(n) time on average?
There is one loop, and hash-set operations are O(1) on average. Python sets are hash tables: they are not ordered and do not use binary search.
3. A learner moves album.add(x) above the if x in album: check. Which input now gives a wrong answer?
With the insert first, the very first number finds itself in the set, so any non-empty list returns True. That only matters when the right answer is False, which among these is [1, 2, 3]; the empty list never enters the loop.
Score 60% or more and the lesson is marked complete.