Topic · Hash MapEasy
Contains Duplicate
Understand the problem
You're given an integer array nums. Return true if any element appears at least twice. Return false if all elements are distinct.
Example:
ts
nums = [1, 2, 3, 1]
output = true // because 1 appears twice
nums = [1, 2, 3, 4]
output = false // all elements are distinctThis problem is a basic check of whether you can use a Hash Map to track the elements you've already seen.
Show the basic approach (slower)
Basic approach
O(n²) time, O(1) spacets
function containsDuplicate(nums: number[]): boolean {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] === nums[j]) return true
}
}
return false
}Why this approach is slow:
Every element is compared with all the remaining elements.
This uses little memory but is very slow for large n.
Optimal solution
Optimal
O(n) time, O(n) spacets
function containsDuplicate(nums: number[]): boolean {
const seen = new Set<number>()
for (const num of nums) {
if (seen.has(num)) return true
seen.add(num)
}
return false
}Key insight:
Use a Set rather than a Hash Map since you only need to know whether an element has appeared, not store its index.
- This is the best approach: each insert and lookup is O(1) amortized.
- As soon as you meet an element that's already in the Set → stop, no need to scan the whole array.
Step-by-step trace
Step through the run — click a step to see its line of code
1function containsDuplicate(nums: number[]): boolean {2 const seen = new Set<number>()3 for (const num of nums) {4 if (seen.has(num)) return true5 seen.add(num)6 }7 return false8}Edge cases to remember
Empty array — no elements, return false.
Single-element array — no duplicates possible, return false.
All elements identical [5, 5, 5] — detected at the 2nd element.
Negative numbers and 0 — a Set handles every integer correctly, negatives included.