Problem
Given an integer array nums, return true if any value appears at least twice.
Example
Input: [1,2,3,1]
Output: trueInput: [1,2,3,4]
Output: falseSolution
Hash set tracks seen values. If we encounter a value already in the set, we found a duplicate.
def contains_duplicate(nums):
return len(nums) != len(set(nums))function containsDuplicate(nums) {
return new Set(nums).size !== nums.length;
}bool containsDuplicate(vector<int>& nums) {
unordered_set<int> seen;
for (int n : nums) {
if (seen.count(n)) return true;
seen.insert(n);
}
return false;
}import java.util.HashSet;
import java.util.Set;
public boolean containsDuplicate(int[] nums) {
Set<Integer> seen = new HashSet<>();
for (int n : nums) {
if (!seen.add(n)) return true;
}
return false;
}Complexity
- Time: O(n)
- Space: O(n)
Explanation
Hash set lookups are O(1) on average. Trade space for time. Alternative: sort and check adjacent elements (O(n log n) time, O(1) space).
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?