Here’s the question link on LeetCode 442. Find All Duplicates in an Array:
https://leetcode.com/problems/find-all-duplicates-in-an-array/description
Contents
Brute Force – O(n^2)
The simplest approach is to check every element against the remaining elements.
If I find the same number again, it’s a duplicate.
To avoid adding the same duplicate more than once, I can maintain a set of numbers I’ve already added to the answer.
class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
int n = nums.size();
vector<int> ans;
unordered_set<int> seen;
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
if(nums[i] == nums[j] &&
seen.find(nums[i]) == seen.end()) {
ans.push_back(nums[i]);
seen.insert(nums[i]);
}
}
}
return ans;
}
};
Better O(n log n)
Can we avoid the nested loops?
What if we sort the array first?
Once sorted, all duplicate elements will be next to each other.
For example:
[4,3,2,7,8,2,3,1]
After sorting:
[1,2,2,3,3,4,7,8]
Now we just traverse the array and check whether the current element is equal to the previous one.
class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<int> ans;
for(int i = 1; i < nums.size(); i++) {
if(nums[i] == nums[i-1]) {
ans.push_back(nums[i]);
}
}
return ans;
}
};
Optimal O(n)
Now here’s the interesting part.
The problem tells us that every number is between 1 and n.
So, we can actually use the array itself to keep track of which numbers we’ve already seen!
Think about it:
- Number
1corresponds to index0. - Number
2corresponds to index1. - Number
3corresponds to index2.
And so on.
We can use the sign of the element at that index to mark whether we’ve seen a number before.
The idea:
- Pick a number
x. - Go to index
x - 1. - If the value there is positive, mark it negative. This is our first occurrence.
- If it’s already negative, we’ve seen this number before. Add it to our answer.
class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
vector<int> ans;
for(int i = 0; i < nums.size(); i++) {
int x = abs(nums[i]);
int idx = x - 1;
if(nums[idx] < 0) {
ans.push_back(x);
}
else {
nums[idx] *= -1;
}
}
return ans;
}
};
Code lines explained
abs(nums[i])gets the original number because we might have already marked this position negative.x - 1gives us the index corresponding to that number.- If
nums[idx]is already negative, we’ve encountered this number before. Add it to the answer. - Otherwise, make it negative to mark that we’ve seen it.
Note: This approach modifies the input array.