Contains Duplicate: Efficiently Checking for Duplicates
The Prompt
Given an integer array `nums`, return `true` if any value appears at least twice in the array, and return `false` if every element is distinct.
Understanding the Problem
The question sounds almost too simple: does any value appear twice? The brute force compares every element against every other element — O(n²) comparisons for a yes/no answer. Sorting first brings duplicates side by side and cuts it to O(n log n), but you are still doing more work than the question demands.
Reframe it as a memory problem: walk the array once and, at each element, ask "have I seen this exact value before?" If you can answer that question in constant time, the whole scan is O(n). Constant-time membership is precisely what a hash set provides.
The Interview Flow
Interviewer
Given an array of integers, how would you determine if it contains any duplicates?
Candidate
A simple way is to compare every element with every other element, but that would be O(n^2). A better approach would be to sort the array first. If there are duplicates, they will be adjacent after sorting. I could then iterate through the sorted array and check for consecutive identical elements. This would be O(n log n) because of the sort.
Interviewer
That's a good improvement. Is there a way to do it in linear time?
Candidate
Yes, I can use a hash set. I would iterate through the array, and for each element, I'd check if it's already in the set. If it is, I've found a duplicate and can return true. If not, I add the element to the set. If I finish the loop without finding duplicates, I return false. This gives O(n) time and O(n) space complexity.
Interviewer
Perfect. Let's go with that approach.
Why does a hash set work here?
The invariant is simple: after processing index i, the set contains exactly the values seen in nums[0..i]. So when the scan reaches a value already in the set, that value must have appeared at an earlier index — a duplicate, guaranteed, with no need to know where. And if the scan finishes with no hit, every insertion was a first sighting, so all elements are distinct.
The trade-off, stated plainly: O(n) extra space buys O(n) time, versus O(1) space at O(n log n) for the sorting approach. Mentioning both — and that the set version can also exit early the moment a duplicate appears — is the interview answer.
Optimal Solution using a Hash Set
- Initialize an empty hash set.
- Iterate through each number in the input array `nums`.
- For each number, check if it already exists in the hash set.
- If the number is in the set, a duplicate has been found, so return `true`.
- If the number is not in the set, add it to the set.
- If the loop completes without finding any duplicates, it means all elements are distinct, so return `false`.
Try it yourself
Write your solution and run it against 4 test cases.
JavaScript, TypeScript & Python run sandboxed in your browser; other languages run on the execution server. Your code is saved locally as you type.
Final Solution
function containsDuplicate(nums) {
const seen = new Set();
for (const num of nums) {
if (seen.has(num)) {
return true;
}
seen.add(num);
}
return false;
}Explanation
Scan nums = [1, 2, 3, 1] and watch the set catch the repeat.
1i = 0: is 1 in the set? No — the set is empty. Insert it: set = {1}.
2i = 1 and i = 2: neither 2 nor 3 is in the set yet, so both are inserted. Set = {1, 2, 3}.
3i = 3: 1 is already in the set (inserted back at index 0). Duplicate found — return true immediately.
Complexity Analysis
TIME
O(n)
SPACE
O(n)
Finished working through this one?
Mark it complete to track it on your Data Structures path.