Part 2 · Problems · Arrays and hashing
Contains Duplicate
#217 · Easy · LeetCode
Return true if any value appears at least twice in the array.
[1,2,3,1] -> true [1,2,3,4] -> false
Ask before coding
- Empty array returns false?
- Can I use extra memory?
Hint
What data structure answers 'have I seen this?' in O(1)?
Approach
Put values in a Set while walking. If one is already there, return true.
Time O(n) Space O(n)
Watch it run
Solution (JavaScript, tested)
function containsDuplicate(nums) {
const seen = new Set();
for (const n of nums) {
if (seen.has(n)) return true;
seen.add(n);
}
return false;
}Traps
- Sorting works too (O(n log n), O(1) extra). Mention the trade-off.
- One-liner: new Set(nums).size !== nums.length, but it can't stop early.
Say out loud: A set gives O(1) membership checks, so one pass. If memory were tight I'd sort and compare neighbours instead.