Question: Given an array of integers, 1 to n, each element is in between 1<a[i]<=n, some elements appear twice and others appear once.
Find all the elements that appear twice in this array.
Brute Force: O(n^2).
The brute force way of solving this problem would be to loop over each element, and for each element check if we see that element again in the array.
var findDuplicates = function(nums) {
let count = 0;
let res = [];
for(let i=0;i<nums.length;i++){
for(let j=i+1;j<nums.length;j++){
if(nums[i] == nums[j]) res.push(nums[i]);
}
}
return res;
};
You guessed it, a smarter way of doing the same would be to sort the array and compare if the adjacent elements if they're same.
Sorting: O(nlogn)
var findDuplicates = function(nums) {
nums.sort((a,b)->a-b);
let count = 0;
for(int i=0;i<nums.length-1;i++){
if(nums[i] == nums[i+1]) res.push(nums[i]);
}
return res;
};
It's cute but not good enough, and as you might have guessed from my other posts, whenever it's about increasing speed, think about how can you use hashmap, since they give you the superpower of accessing entries in O(1) time. In this case a Set will also do the work.
HashMaps: O(n) time and O(n) space.
So we shall create an object, add each element to them and check if we've seen that element before, if we've seen the element before, then add it to result.
var findDuplicates = function(nums) {
let map = {};
let res = [];
for(let num of nums){
if(!map[num]){
map[num] = true;
}else{
res.push(num);
}
}
return res;
};
Now if you've reached till here, believe me you did a great job.
But to get that FAANG tag and make your ex jealous, we have to figure out a way to solve this problem in O(n) time with O(1) space.
So, let's think about this problem more closely,
1> the problem states that each element, a[i], is in between 1 and n. So if the length of the array is 5, then each element is 1<= a[i]<=5.
2> the array elements are indexed from 0 to n-1.
Can we take advantage of these two observations to achieve our goal?
index : 0 1 2 3 4 5 6 7
nums : 4 3 2 7 8 2 3 1
let's create a boolean array, the same length as the length of given array, and whenever for each element we set the corresponding array(nums[index] - 1) to true.
arr : f f f f f f f f
Let's iterate over the array and mark the corresponding index to true.
index : 0, nums[0] = 4, set arr[4-1] = arr[3] to true;
index : 0 1 2 3 4 5 6 7
nums : 4 3 2 7 8 2 3 1
arr : f f f t f f f f
index : 1, nums[1] = 3, set arr[3-1] = arr[2] to true;
index : 0 1 2 3 4 5 6 7
nums : 4 3 2 7 8 2 3 1
arr : f f t t f f f f
index : 2, nums[2] = 2, set arr[2-1] = arr[1] to true;
index : 0 1 2 3 4 5 6 7
nums : 4 3 2 7 8 2 3 1
arr : f t t t f f f f
index : 3, nums[3] = 7, set arr[7-1] = arr[6] to true;
index : 0 1 2 3 4 5 6 7
nums : 4 3 2 7 8 2 3 1
arr : f t t t f f t f
index : 4, nums[4] = 8, set arr[8-1] = arr[7] to true;
index : 0 1 2 3 4 5 6 7
nums : 4 3 2 7 8 2 3 1
arr : f t t t f f t t
index : 5, nums[5] = 2, set arr[2-1] = arr[1] to true;
Here we see that arr[1] is already set to true,
this means its a duplicate hence add nums[5] to result.
index : 0 1 2 3 4 5 6 7
nums : 4 3 2 7 8 2 3 1
arr : f t t t f f t t
index : 6, nums[6] = 3, set arr[3-1] = arr[2] to true;
Here we see that arr[2] is already set to true,
this means its a duplicate hence add nums[6] to result.
index : 0 1 2 3 4 5 6 7
nums : 4 3 2 7 8 2 3 1
arr : f t t t f f t t
index : 7, nums[7] = 1, set arr[1-1] = arr[0] to true;
index : 0 1 2 3 4 5 6 7
nums : 4 3 2 7 8 2 3 1
arr : t t t t f f t t
We ve reached end of the array and the result is [2,3]
But you might be wondering why to bother doing this when we can achieve the same using hashmap.
In order to run it in O(n) time and O(1) space and impress your interviewer and crush, let's make a modification, instead of creating a new boolean array, we shall mark the element as negative. Let's see how:
Let's repeat the whole song and dance:
*Note: at for each element we absolute its value to get the index.
index : 0, nums[0] = 4, set nums[4-1] = nums[3] to -ve;
index : 0 1 2 3 4 5 6 7
nums : 4 3 2 -7 8 2 3 1
index : 1, nums[1] = 3, set nums[3-1] = nums[2] to -ve;
index : 0 1 2 3 4 5 6 7
nums : 4 3 -2 -7 8 2 3 1
index : 2, nums[2] = 2, set nums[2-1] = nums[1] to -ve;
index : 0 1 2 3 4 5 6 7
nums : 4 -3 -2 -7 8 2 3 1
index : 3, nums[3] = 7, set nums[7-1] = nums[6] to -ve;
index : 0 1 2 3 4 5 6 7
nums : 4 -3 -2 -7 8 2 -3 1
index : 4, nums[4] = 8, set nums[8-1] = nums[7] to -ve;
index : 0 1 2 3 4 5 6 7
nums : 4 -3 -2 -7 8 2 -3 -1
index : 5, nums[5] = 2, set nums[2-1] = nums[1] to -ve;
but nums[1] = -3 is already negative, so push (1+1) to result.
index : 0 1 2 3 4 5 6 7
nums : 4 -3 -2 -7 8 2 -3 -1
index : 6, nums[6] = 3, set nums[3-1] = nums[2] to -ve;
but nums[2] = -2 is already negative, so push (2+1) to result.
index : 0 1 2 3 4 5 6 7
nums :-4 -3 -2 -7 8 2 -3 -1
index : 7, nums[7] = 1, set nums[1-1] = nums[0] to -ve;
index : 0 1 2 3 4 5 6 7
nums :-4 -3 -2 -7 8 2 -3 -1.
we have reached the end of the iteration. [2,3] is the result.
Let's convert it to code:
var findDuplicates = function(nums) {
var res = [],
index,
i;
for(i = 0; i < nums.length; i++){
index = Math.abs(nums[i]) - 1;
if(nums[index] < 0)
res.push(index + 1);
else
nums[index] *= -1;
}
return res;
};
I hope you understood the explanation, it's not the most intuitive solution but once you solve it 2/3 times you'll get hang of it. If any doubts feel free to comment down below :)
Happy to help! Go nail that coding interview, get an awesome job, you're ex jealous. :P
Top comments (0)