DEV Community is a community of 788,722 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Akhil

Posted on • Updated on

Find All Duplicates in an Array

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.

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 = 4, set arr[4-1] = arr 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 = 3, set arr[3-1] = arr 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, set arr[2-1] = arr 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 = 7, set arr[7-1] = arr 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 = 8, set arr[8-1] = arr 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 = 2, set arr[2-1] = arr to true;
Here we see that arr is already set to true,
this means its a duplicate hence add nums 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 = 3, set arr[3-1] = arr to true;
Here we see that arr is already set to true,
this means its a duplicate hence add nums 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 = 1, set arr[1-1] = arr 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 = 4, set nums[4-1] = nums to -ve;
index : 0  1  2  3  4  5  6  7
nums  : 4  3  2 -7  8  2  3  1

index : 1, nums = 3, set nums[3-1] = nums to -ve;
index : 0  1  2  3  4  5  6  7
nums  : 4  3 -2 -7  8  2  3  1

index : 2, nums = 2, set nums[2-1] = nums to -ve;
index : 0  1  2  3  4  5  6  7
nums  : 4 -3 -2 -7  8  2  3  1

index : 3, nums = 7, set nums[7-1] = nums to -ve;
index : 0  1  2  3  4  5  6  7
nums  : 4 -3 -2 -7  8  2 -3  1

index : 4, nums = 8, set nums[8-1] = nums to -ve;
index : 0  1  2  3  4  5  6  7
nums  : 4 -3 -2 -7  8  2 -3 -1

index : 5, nums = 2, set nums[2-1] = nums to -ve;
but nums = -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 = 3, set nums[3-1] = nums to -ve;
but nums = -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 = 1, set nums[1-1] = nums 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 