Find duplicates in an array in most efficient way

Display all the elements which are duplicates in most efficient way in O(n) and O(1) space.

Given an array of size n which contain numbers from range 0 to n-1, these numbers can occur any number of times. finding all the duplicate numbers in that array. That is if the number as already occured in the array, then the number is duplicate.

Example

INPUT

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 7 1 0 0 0

ALGORITHM 1

TIME COMPLEXITY – O(N)
SPACE COMPLEXITY – O(1)

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 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.

C++ Program

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int arr[] = {1,5,4,2,8,4,1,0,0,2,4,9,4,2,4,6,6,7,3,1,0,0,0};
	int N = sizeof(arr)/sizeof(arr[0]);
	
	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;
}
Try It


Next > < Prev
Scroll to Top