Approach Summary
Add each element to a Set; return true the moment a duplicate is found.
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Sorting and Adjacent Check | O(n log n) | O(1) or O(log n) | Sort the array so duplicate numbers become adjacent, then verify neighbors. |
| 2 Approach 2: Hash Set Lookup (Optimal) | O(n) | O(n) | Use a hash set to detect previously encountered elements in linear time. |
Approach 1: Sorting and Adjacent Check
By sorting the array in non-decreasing order, any duplicate values will be placed directly adjacent to each other. We then perform a single linear sweep comparing nums[i] with nums[i - 1]. This avoids O(n) extra hash table memory at the cost of O(n log n) sorting time.
Approach 1: Sorting and Adjacent Check Implementation
Approach 1: Sorting and Adjacent Check
class Solution {
public boolean containsDuplicate(int[] nums) {
Arrays.sort(nums);
for (int i = 1; i < nums.length; i++) {
if (nums[i] == nums[i - 1]) {
return true;
}
}
return false;
}
}class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
sort(nums.begin(), nums.end());
for (int i = 1; i < (int)nums.size(); i++) {
if (nums[i] == nums[i - 1]) {
return true;
}
}
return false;
}
};def contains_duplicate(nums: list[int]) -> bool:
nums.sort()
for i in range(1, len(nums)):
if nums[i] == nums[i - 1]:
return True
return Falsefunction containsDuplicate(nums) {
nums.sort((a, b) => a - b);
for (let i = 1; i < nums.length; i++) {
if (nums[i] === nums[i - 1]) return true;
}
return false;
}Approach 2: Hash Set Lookup (Optimal)
Iterate through the array and check whether each element already exists in a hash set. If it exists, return true immediately. If not, add the element to the set. If the loop completes without finding any duplicate, return false. This is the optimal industry-standard solution.
Approach 2: Hash Set Lookup (Optimal) Implementation
Approach 2: Hash Set Lookup (Optimal)
class Solution {
public boolean containsDuplicate(int[] nums) {
int n = nums.length;
Set<Integer> set = new HashSet<>();
for (int i = 0; i < n; i++) {
if (set.contains(nums[i])) {
return true;
}
set.add(nums[i]);
}
return false;
}
}class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
int n = nums.size();
unordered_set<int> setBucket;
for (int i = 0; i < n; i++) {
if (setBucket.find(nums[i]) != setBucket.end()) {
return true;
}
setBucket.insert(nums[i]);
}
return false;
}
};def contains_duplicate(nums: list[int]) -> bool:
seen = set()
for num in nums:
if num in seen:
return True
seen.add(num)
return Falsefunction containsDuplicate(nums) {
const seen = new Set();
for (const num of nums) {
if (seen.has(num)) return true;
seen.add(num);
}
return false;
}Edge Cases to Watch
- Single-element array (always false)
- Array with all identical elements
- Negative and positive numbers mixed
- Large arrays with duplicate at the very start or end
Master the Hash Map / Set Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Hash Map / Set pattern.
How to Recognize This Pattern
- Existence check across all previous elements
- Set is O(1) lookup vs O(n) scan
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(n)