Contains Duplicate
EasyArrays and hashing
Given an array of integers nums, return true if any value appears at least twice, and false if every value is different.
Examples
Input: nums = [3, 8, 1, 8] Output: true
8 appears twice.
Input: nums = [4, 5, 6] Output: false
All three values are different.
Constraints
1 ≤ nums.length ≤ 10⁵-10⁹ ≤ nums[i] ≤ 10⁹
Stuck?
Hint 1
Comparing every pair works, but it takes O(n²) time.
Hint 2
A Set remembers what you have seen. If a number is already in it, you have your answer.
The idea
A repeat is a value you meet for the second time. Remember every value you pass in a Set: the first value that is already in it is a repeat. A Set tells you whether it holds a value in constant time, so one pass is enough.
Time O(n)Extra space O(n)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 4
seen holds every value passed so far. Checking it takes constant time, where scanning the earlier values again would need a second loop.
function containsDuplicate(nums) { const seen = new Set(); for (const n of nums) { if (seen.has(n)) return true; seen.add(n); } return false;}The trap
Comparing each value only with the one next to it finds a repeat when the two copies sit side by side, so a run of equal values passes. Copies with other values between them are never compared, and the answer is false. Sorting first would put the copies together, at O(n log n) time.
function containsDuplicate(nums) { // only neighbours: misses repeats that are apart for (let i = 0; i + 1 < nums.length; i++) if (nums[i] === nums[i + 1]) return true; return false;}