#217
Contains Duplicate
Easy HashSet
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return true if any value appears at least twice in the array.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: does any value repeat?
Why this works: add to a set; a failed add means a repeat.
Example: [1, 2, 3, 1]
add 1, 2, 3 ✓, add 1 ✗ → true✦Hints open one at a time
A HashSet remembers what you've seen in O(1) per lookup.
Set.add returns false if the value was already present.
↗Approach
Add each value to a HashSet; the first failed add means a duplicate.
</>Solution (Java)
import java.util.*;
class Solution {
public boolean containsDuplicate(int[] nums) {
Set<Integer> seen = new HashSet<>();
for (int x : nums) {
if (!seen.add(x)) return true; // already there
}
return false;
}
}!Common mistake
Using a List and contains() — that's O(n) per check, O(n²) overall.
Complexity
- Time: O(n).
- Space: O(n).
Topic: Hashing
🎬 Episodes 37–39: video coming soon