Know this before you start: “Use a set to check “have I seen this?””
A set for “have I seen this?”
A set holds unique items and answers “is x in here?” in O(1). Check it before adding as you walk, and duplicates jump out.
The idea
A set is like a hash map with only keys: it stores each item once and checks membership in O(1) on average. A list needs O(n) for the same check, because it looks at every item.
The pattern: walk the input; for each item first ask the set whether you've met it, then add it. That turns many “did this appear earlier?” problems from O(n²) into O(n).
See it step by step
Does [3, 1, 4, 1, 5] contain a duplicate?
- 3: not in {} → add → {3}
- 1: not in {3} → add → {3, 1}
- 4: not in {3, 1} → add → {3, 1, 4}
- 1: already in the set → duplicate found, stop.
In code (Python)
def has_duplicate(nums):
seen = set()
for x in nums:
if x in seen: # O(1) check
return True
seen.add(x)
return False
print(has_duplicate([3, 1, 4, 1, 5])) # True
print(has_duplicate([3, 1, 4])) # FalseO(n) time, O(n) space.
When you'll use it
- Duplicates, “first repeated”, “unique values”, “longest consecutive run”.
- Remembering visited positions in grids and graphs.
Common mistakes
- Using `x in my_list` inside a loop: that's O(n²) overall.
- Adding before checking, so every item “finds itself”.
