Contains Duplicate looks almost too simple to deserve a full breakdown. Given an array, does any value show up more than once? But the path from “the obvious approach” to “the fast approach” isolates a decision that quietly shows up in a huge amount of real code: knowing exactly when a loop should become a set.
The naive approach
The first instinct, like with most array problems, is to check every number against every other number:
nums = [1, 2, 3, 4, 5, 1]
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] == nums[j]:
print("Duplicate found:", nums[i])Works fine on small inputs. But it’s O(n²) — the same scaling issue we ran into with Two Sum.
A step up: sorting first
A common next idea is to sort the array, then check neighboring elements:
nums_sorted = sorted(nums)
for i in range(len(nums_sorted) - 1):
if nums_sorted[i] == nums_sorted[i + 1]:
print("Duplicate found:", nums_sorted[i])Better — sorting costs O(n log n), a real improvement over O(n²). But it’s still not the best available.
The actual fix
Instead of comparing values to each other, ask one question per number: “have I already seen this exact value?”
def contains_duplicate(nums):
seen = set()
for num in nums:
if num in seen:
return True
seen.add(num)
return FalseOne pass, one set, O(n).
Set vs. dictionary — the actual decision point
This is the part worth remembering beyond this one problem: use a set when you only need yes/no memory — “have I seen this?” Use a dictionary when you need to remember a value alongside something else, like its position (as in Two Sum, where you needed to know not just that a number was seen, but where).
| Approach | Time Complexity |
|---|---|
| Brute force (nested loop) | O(n²) |
| Sort then scan | O(n log n) |
| Set lookup | O(n) |
What’s next
This is Video 2 in Think in Patterns, Not Problems. Same core instinct as Two Sum — trading memory for speed — applied slightly differently. Next video builds on this again with a new pattern.
Watch the full walkthrough: https://youtu.be/4gc9tPVuIuk
Full playlist: https://www.youtube.com/playlist?list=PLTyiXpqKeCvQ
