217. Contains Duplicate
🟩 Easy
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 1
Input: nums = [1,2,3,1] Output: true
Example 2
Input: nums = [1,2,3,4] Output: false
Example 3
Input: nums = [1,1,1,3,3,4,3,2,4,2] Output: true
Constraints
1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
Solution
My Solution (Hash Map)
func containsDuplicate(nums []int) bool {
if len(nums) < 2 {
return false
}
m := make(map[int]bool)
for _, num := range nums {
if _, ok := m[num]; ok {
return true
}
m[num]=true
}
return false
}
Optimal Solution 1 (Memory-Efficient Set)
func containsDuplicate(nums []int) bool {
seen := make(map[int]struct{})
for _, num := range nums {
if _, exists := seen[num]; exists {
return true
}
seen[num] = struct{}{}
}
return false
}
Optimal Solution 2 (Sorting)
func containsDuplicate(nums []int) bool {
sort.Ints(nums)
for i := 1; i < len(nums); i++ {
if nums[i] == nums[i-1] {
return true
}
}
return false
}
Approach Analysis
This problem demonstrates multiple efficient approaches:
Hash Map (Your Solution):
Track seen numbers with bool values
Early termination on finding duplicate
Simple and effective approach
Good balance of time and space
Memory-Efficient Set:
Uses empty struct instead of bool
Same logic as hash map
More memory efficient
Idiomatic Go solution
Sorting Approach:
Trade time for space
No extra memory needed
Simple adjacent comparison
Modifies input array
Visualization of Both Approaches
Hash Map Process (Your Solution)
Input: [1,2,3,1]
Step 1: map = {}
Step 2: map = {1: true}
Step 3: map = {1: true, 2: true}
Step 4: map = {1: true, 2: true, 3: true}
Step 5: Check 1 → found in map → return true
Memory-Efficient Set Process
Input: [1,2,3,1]
Step 1: set = {}
Step 2: set = {1: struct{}{}}
Step 3: set = {1: struct{}{}, 2: struct{}{}}
Step 4: set = {1: struct{}{}, 2: struct{}{}, 3: struct{}{}}
Step 5: Check 1 → exists → return true
Sorting Process
Input: [1,2,3,1]
Step 1: Sort → [1,1,2,3]
Step 2: Compare adjacent:
1 == 1 → return true
Complexity Analysis
Hash Map Solution (Your Solution)
Time: O(n)
Single pass through array
O(1) map operations
Early termination possible
Space: O(n)
Stores all unique elements
Uses bool values
Worst case: all unique
Memory-Efficient Set
Time: O(n)
Same as hash map
O(1) set operations
Early termination
Space: O(n)
Stores unique elements
Uses empty struct (0 bytes)
More memory efficient
Sorting Solution
Time: O(n log n)
Dominated by sorting
Linear scan after sort
No early termination
Space: O(1)
In-place sorting
No extra storage
Modifies input array
Why Solutions Work
Hash Map Logic:
Each number seen once
Instant lookup
Returns on first duplicate
Simple hash table principle
Set Logic:
Set ensures uniqueness
Memory optimization
Same time complexity
More space efficient
Sorting Logic:
Duplicates become adjacent
One-pass comparison
Space-time tradeoff
Simple implementation
When to Use
Hash Map/Set When:
Can't modify input
Memory available
Need early termination
Average case performance
Sorting When:
Memory constrained
Can modify input
Order useful later
Simplicity preferred
Common Patterns & Applications
Related Problems:
Contains Duplicate II
Contains Duplicate III
Find All Duplicates
Find the Duplicate Number
Key Techniques:
Hash table usage
Set operations
In-place sorting
Space-time tradeoffs
Interview Tips
Solution Highlights:
Discuss tradeoffs
Mention optimizations
Consider constraints
Handle edge cases
Common Pitfalls:
Unnecessary length checks
Not considering memory
Missing edge cases
Inefficient lookups
Testing Strategy:
Empty array
Single element
All duplicates
No duplicates
Large arrays
Follow-up Questions:
Memory constraints?
Maintain order?
Stream processing?
Parallel solution?

Leetcode: link
Last updated
Was this helpful?