Contains Duplicate
Problem statement
You are given a list of integers nums. Return true if any value shows up
two or more times in the list, and false if every value is different.
Think of nums as a list of ports handed out to different services. Before
deploying, you want a quick check: was the same port accidentally given to two
services?
Examples
Example 1
Input: nums = [1, 2, 3, 1]
Output: true
Explanation: The value 1 shows up at index 0 and again at index 3, so the list has a duplicate.
Example 2
Input: nums = [1, 2, 3, 4]
Output: false
Explanation: Every value in the list is different, so there is no duplicate.
Example 3
Input: nums = [1, 1, 1, 3, 3, 4, 3, 2, 4, 2]
Output: true
Explanation: Several values repeat here (1, 3, 4 and 2 each show up more than once), so a duplicate exists — the list can have more than one repeated value, but only one true/false answer is needed.
Hints
Approach
Optimal: Hash set
Intuition
Sorting works, but it spends effort putting the whole list in order when all you actually need is a fast way to ask "have I seen this value before?". A hash set answers that question in roughly constant time, so a single pass through the list — checking and then remembering each value — is enough.
For each value, check whether it is already in the set. If it is, you've found a duplicate immediately, without needing to look at the rest of the list. If not, add it to the set and move on.
Steps
- Create an empty set called
seen. - Walk through
nums, looking at one valuexat a time. - If
xis already inseen, a duplicate is found — returntrue. - Otherwise, add
xtoseenand continue. - If the loop finishes with no match, return
false.
Edge case: a list with zero or one value can never contain a duplicate — the set never has a chance to already hold the single value being checked, so the loop correctly falls through to false.
Complexity
Time O(n) - a single pass over the list, and each set lookup or insert takes constant time on average
Space O(n) - in the worst case (no duplicate at all) the set ends up holding every value in the list
class Solution:
def containsDuplicate(self, nums: list[int]) -> bool:
seen = set()
for x in nums:
if x in seen:
return True
seen.add(x)
return False
if __name__ == "__main__":
print(str(Solution().containsDuplicate([1, 2, 3, 1])).lower()) # true
print(str(Solution().containsDuplicate([1, 2, 3, 4])).lower()) # false
print(str(Solution().containsDuplicate([1, 1, 1, 3, 3, 4, 3, 2, 4, 2])).lower()) # trueRecapThe whole problem in a few lines, for the night before
- Spot it: "does any value repeat?" in an unsorted list
- Idea: keep a set of values seen so far; the first value already in the set is a duplicate
- Cost: O(n) time, O(n) space (sorting first: O(n log n) time, O(n) space for a copy, or O(1) extra if sorted in place)
- Trap: comparing every pair works but is O(n²) — too slow once the list gets into the tens of thousands
- Remember:
len(set(nums)) != len(nums)is a correct one-liner, but it always scans the whole list; the loop version can stop at the first duplicate
Interview follow-ups
What if you need to return the duplicate value itself, not just whether one exists?
Use the same hash set, but instead of returning
truethe moment you find a match, save that value and either return it right away (if you only need the first duplicate) or keep scanning and collect every repeated value into a list. The time stays O(n); you just do something with the match instead of stopping immediately.The list is too large to fit in memory and arrives as a stream. What would you do?
An exact answer still needs to remember every value seen so far, so you either shard the stream by hash (equal values always land in the same shard, so you can check each shard on its own, smaller machine) or accept a small chance of error using a fixed-memory structure like a Bloom filter, which can say "no duplicate" with certainty but only "probably a duplicate" when it flags one.
Frequently asked questions
That one-liner is correct and also O(n) — a set can only hold each distinct
value once, so if the set ends up smaller than the original list, something
repeated. The loop version does the same amount of work in the worst case,
but it can return true the moment it spots the first duplicate, instead of
always building the entire set first.
When memory is limited and you're allowed to reorder the input. Sorting in place needs almost no extra memory (O(1) beyond the sort itself), while the hash set approach can grow to hold every value in the list. The trade-off is that sorting changes the order of the caller's data, which may not be acceptable.
Both cases correctly return false in every approach here — there's no
second value to compare against, so no duplicate can exist.
Starting the inner loop at the same index as the outer one instead of one
past it. If both loops start at 0, the code ends up comparing every value
with itself (nums[i] == nums[i] is always true), which reports a duplicate
even when the list has none. Starting the inner loop at i + 1 guarantees
the two indices are always different.
Checking a list of hostnames, IPs, ports or config keys for repeats is a real pre-deploy sanity check. The same "have I seen this before" set is also the first building block for deduplicating alerts or collapsing repeated log lines.
