BeginnerArrays & Strings
“Have I seen this?” is a set
Checking whether you've met a value before? Put values in a set as you go: each check is O(1) instead of a scan.
The idea
Many problems secretly ask “have I seen this value already?”. Scanning back through the array each time is slow. A set answers that question in O(1) on average.
The pattern: walk the input once; for each value, first check the set, then add the value.
Worked example
Contains Duplicate on [1, 2, 3, 1]
- 1 → not in {} → add → {1}
- 2 → not in {1} → add → {1, 2}
- 3 → not in {1, 2} → add → {1, 2, 3}
- 1 → in the set → return True
In code (Python)
def contains_duplicate(nums):
seen = set()
for x in nums:
if x in seen:
return True
seen.add(x)
return FalseO(n) time, O(n) space for the set.
How to spot it
- “duplicate”, “appears twice”, “unique”, “first repeated”.
- You catch yourself writing a loop inside a loop just to look something up.
Common mistakes
- Adding before checking, so every value finds itself.
- Using a list instead of a set: `in` on a list is O(n).
Practise it
Go further
Up next for you · Beginner
Counting things with a hash map →