DEV Community

Akhil
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;
};
Enter fullscreen mode Exit fullscreen mode

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;
};
Enter fullscreen mode Exit fullscreen mode

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;
};
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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 
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

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.
Enter fullscreen mode Exit fullscreen mode

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;
};

Enter fullscreen mode Exit fullscreen mode

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

githhub: https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/findAllDuplicatesInAnArray.js

Buy Me A Coffee

Discussion (0)