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.Example
nums = [1, 2, 3, 1]
Output: true
The value 1 appears at both index 0 and index 3, so the array contains a duplicate.
Use a hash set to track numbers you've already seen as you walk through the array. For each number, check if it's already in the set — if so, you've found a duplicate. This gives you O(1) lookups instead of scanning the whole array each time.
Why this works
A hash set gives you O(1) lookups. As you walk through the array, you check whether each number has been seen before. The moment you find one that has, you know there is a duplicate – no need to check the rest.
Step by step
- Create an empty set — this will store every unique number you encounter.
- Check before adding — for each number, ask “is this already in the set?” If yes, return true immediately.
- Add and continue — if the number is new, insert it into the set and move to the next element.
- No duplicates found — if you finish the loop without a hit, return false.
Time: O(n)
Space: O(n)
class Solution {
public boolean containsDuplicate(int[] nums) {
Set<Integer> seen = new HashSet<>();
for (int num : nums) {
if (!seen.add(num)) { // add returns false if already present
return true;
}
}
return false;
}
}
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
unordered_set<int> seen;
for (int num : nums) {
if (seen.count(num)) { // already encountered this number
return true;
}
seen.insert(num);
}
return false;
}
};
def containsDuplicate(nums: list[int]) -> bool:
seen = set()
for num in nums:
if num in seen: # already encountered this number
return True
seen.add(num) # remember it for future checks
return False