# Find Duplicates in an Array in Most Efficient Way

Difficulty Level Easy
Frequently asked in Amazon Apple Bloomberg Facebook Google lyft Microsoft Paytm Pocket Gems Qualcomm Zoho
ArrayViews 3608

Table of Contents

## Problem Statement

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 the most efficient way. That is if the number has 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 used for the implementation of 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.

## Implementation

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

### Java Program for Find Duplicates in an Array in Most Efficient Way

```import java.util.Arrays;
import java.util.Scanner;
class sum
{
public static int abs(int x)
{
if(x<0)
{
return -1*x;
}
else
{
return x;
}
}
public static void main(String[] args)
{
Scanner sr = new Scanner(System.in);
int n = sr.nextInt();
int a[] = new int[n];
for(int i=0;i<n;i++)
{
a[i] = sr.nextInt();
}
int zero = 0; //separate case for zero
for(int i = 0; i < n; i++)
{
if(a[i] == 0)
{
if(zero > 0)
System.out.print(0+" ");
zero++;
}
else if(a[abs(a[i])] >= 0)  // we take the element's value as the index and change the sign of the element at that position
a[abs(a[i])] = - a[abs(a[i])];
else    //if we have duplicates then we will encounter a location whose value is negative
System.out.print(abs(a[i])+" ");
}
}
}```
```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 results.

References

Translate »