Contains Duplicate
Before importing a batch of records, a data pipeline computes a signed integer fingerprint for each record and collects them in nums. If the same fingerprint shows up more than once, the batch probably contains a duplicated record and is held back for review.
Return true if at least one value occurs two or more times in nums, and false if every value is different.
Input: nums = [31,-7,12,-7,5] Output: true
Explanation: The fingerprint -7 occurs at positions 1 and 3.
Input: nums = [100,200,-300,400] Output: false
Explanation: All four fingerprints are different.
Input: nums = [7,3,9,3,7] Output: true
Explanation: Both 3 and 7 repeat; a single repeat is already enough.
Constraints
numscontains between 1 and 10^5 fingerprints.- Each fingerprint is an integer from -10^9 to 10^9.
💡 Hint 1
Comparing every pair works but is O(n²). What would let you answer "have I seen this before?" instantly?
💡 Hint 2
Insert values into a hash set as you scan; the first value already in the set is a duplicate.
💡 Hint 3
Alternatively, sort the array: equal values end up next to each other.
Try it yourself first ✎
Solutions stick better after a real attempt. Peek when you're ready.
Approach
Scan the array once while keeping a hash set of the values seen so far. If the current value is already in the set, a duplicate exists and you can stop early; if the scan finishes, every value was distinct. Sorting and comparing neighbours also works in O(n log n) time with no extra set.
function containsDuplicate(nums) {
const seen = new Set();
for (const x of nums) {
if (seen.has(x)) return true;
seen.add(x);
}
return false;
}class Solution {
public boolean containsDuplicate(int[] nums) {
Set<Integer> seen = new HashSet<>();
for (int x : nums) {
if (!seen.add(x)) return true;
}
return false;
}
}No submissions yet. Press Submit to run your code against every test.
/**
* @param {number[]} nums
* @return {boolean}
*/
function containsDuplicate(nums) {
}Run your code to see results here.