Home » Technical Interview Questions » Array Interview Questions » Find Duplicates in an Array in Most Efficient Way

Find Duplicates in an Array in Most Efficient Way


Reading Time - 3 mins

Display all the elements which are duplicates in the most efficient way in O(n) and O(1) space. Given an array of size n which contains numbers from range 0 to n-1, these numbers can occur any number of times. Find duplicates in an array in most efficient way. That is if the number as already occurred in the array, then the number is duplicate.

Example

Input

23

1 5 4 2 8 4 1 0 0 2 4 9 4 2 4 6 6 7 3 1 0 0 0

Output

4 1 0 2 4 4 2 4 6 1 0 0 0

Approach for Find Duplicates in an Array in Most Efficient Way

Now we understand the problem understand. So, without taking much time we directly move to the algorithm use for implementation the problem.

Algorithm

1.    Take a separate variable for handling the repetition of zero.
2.    Next, traverse the array.
3.    If the element is zero increment count of zero. If the count is greater than 1 then display it as it got duplicated.
4.    If it is other than zero, then go to the index of the array pointed by the absolute value of the element you are standing i.e. arr[abs(arr[i])] and if it is positive then make it negative implying that the element which is the index i has occurred once.
5.    If we get a duplicate then we will see that arr[abs(arr[i])] is already of opposite sign and we can simply print it.

READ  Remove duplicates from sorted array

C++ Program for Find Duplicates in an Array in Most Efficient Way

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N;//size of the array
    cin>>N;
    int arr[N];
    for(int i=0;i<N;i++)
    {
      cin>>arr[i];
    }
    int zero = 0; //separate case for zero
    for(int i = 0; i < N; i++)
    {
    if(arr[i] == 0)
      {
        if(zero > 0)
          cout << 0 << " ";
        
        zero++;
      }
      
    else if(arr[abs(arr[i])] >= 0)  // we take the element's value as the index and change the sign of the element at that position
    arr[abs(arr[i])] = - arr[abs(arr[i])];
    
    else    //if we have duplicates then we will encounter a location whose value is negative
     cout << abs(arr[i]) <<" ";
   }
   return 0;
}
23
1 5 4 2 8 4 1 0 0 2 4 9 4 2 4 6 6 7 3 1 0 0 0
4 1 0 2 4 4 2 4 6 1 0 0 0

Complexity Analysis for Find Duplicates in an Array in Most Efficient Way

Time Complexity

O(N) where N is the number of elements present in the given array, Here we traverse the whole array and compute our answer.

Space Complexity

O(1) because we won’t use auxiliary space in the computation of result.

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions