Find First Repeating Element In An Array

We are going to find the First Repeating Element In An Array but before this, I hope you know what the array, binary search, set is. I am not going to make this post long so let’s start.

Example

Input Array - [1, 2, 3, 4, 3, 5];
First repeated element is 3

Algorithm to find first repeating element in an array

• Using Sorting O(n log(N))
• Another Efficient way Hashing O(n)
• Using Two Nested Loop O(N^2)

Here we are discussing the all the three ways with the code to find first repeating element in an array.

Using Sorting

I assume you know about sorting techniques like the bubble sort, merge sort, etc, and also C++ STL function sort.

Algorithm:

• We first copy the given array to another array named as aux[]
• Sort the elements of aux[]
• Scan the given array from left to right and check each element occurrence in aux[] and the first element that repeats twice is our answer

#include <bits/stdc++.h>
using namespace std;
/* if x is present in arr[] then returns  
   the index of FIRST occurrence  
   of x in arr[0..n-1], otherwise returns -1 */
int first(int arr[], int low, int high, int x, int n) 
{ 
  if(high >= low) 
  { 
    int mid = (low + high)/2;  /*low + (high - low)/2;*/
    if( ( mid == 0 || x > arr[mid-1]) && arr[mid] == x) 
      return mid; 
    else if(x > arr[mid]) 
      return first(arr, (mid + 1), high, x, n); 
    else
      return first(arr, low, (mid -1), x, n); 
  } 
  return -1; 
} 
  
/* if x is present in arr[] then returns the 
   index of LAST occurrence of x in arr[0..n-1],  
   otherwise returns -1 */ 
int last(int arr[], int low, int high, int x, int n) 
{ 
  if (high >= low) 
  { 
    int mid = (low + high)/2;  /*low + (high - low)/2;*/
    if( ( mid == n-1 || x < arr[mid+1]) && arr[mid] == x ) 
      return mid; 
    else if(x < arr[mid]) 
      return last(arr, low, (mid -1), x, n); 
    else
      return last(arr, (mid + 1), high, x, n);       
  } 
  return -1; 
} 
  
/* if x is present in arr[] then returns the count 
   of occurrences of x, otherwise returns -1. */
int count(int arr[], int x, int n) 
{ 
  int i; // index of first occurrence of x in arr[0..n-1] 
  int j; // index of last occurrence of x in arr[0..n-1] 
      
  /* get the index of first occurrence of x */
  i = first(arr, 0, n-1, x, n); 
  
  /* If x doesn't exist in arr[] then return -1 */
  if(i == -1) 
    return i; 
     
  /* Else get the index of last occurrence of x.  
     Note that we are only looking in the subarray  
     after first occurrence */   
  j = last(arr, i, n-1, x, n);      
     
  /* return count */
  return j-i+1; 
} 
int main() {
	
	    int n;
	    cin>>n;
	    int arr[n];
	    for(int i = 0;i<n;i++)
	    cin>>arr[i];
	    
	    int aux[n];
	    for(int i = 0;i<n;i++)
	    aux[i] = arr[i];
	    
	    sort(aux,aux+n); // Sorting the aux[]
	    int check = 0;
	    for(int i = 0;i<n;i++)
	    {
	        if(count(aux,arr[i],n)>1)
	        {
	            cout<<"Repeated Element is "<<arr[i];
	            check = 1;
	            break;
	        }
	    }
	    if(check == 0)
	    cout<<"No element Repeated"<<endl;
	    
	    
	return 0;
}

Input array = [2, 1, 4, 3, 2]

After sorting and adding to aux[] = [1, 2, 2, 3, 4]

Now traversing array from left to right and checking in aux using binary search and we get 2 as our answer.

Hashing:

I assume you know about Set in C++. What I am going to do is

Algorithm

• Add element of array in Set from right
• check from the right hand side and if element is present we add to min variable
• If element is not present we add it to the set

#include <bits/stdc++.h>
using namespace std;
int count(int aux[], int n)
{
    int min = -1; //Initialize with -1
    set<int> s;   // Creating set
    for(int i = n-1;i>=0;i--)
    {
       if (s.find(aux[i]) != s.end())  // finding element to set.
            min = i; 
            
        else
        s.insert(aux[i]);  // adding element to set.
    }
    return min;
}
int main() {
	
	    int n;
	    cin>>n;
	    int arr[n];
	    for(int i = 0;i<n;i++)
	    cin>>arr[i];
	    
	    
	        if(count(arr,n)!=-1)
	        
	            cout<<"Repeated Element is "<<arr[count(arr,n)];
	           else
	    cout<<"No element Repeated"<<endl;
	    
	    
	return 0;
}

Using Two Nested Loop:

This is simplest and most time consuming algorithm, The steps are given below

• Make two nested loop
• Outer loop picks up element
• Inner loop counts occuerence in array

#include <bits/stdc++.h>
using namespace std;
int count(int aux[], int n)
{
    for(int i = 0;i<n;i++)
    {
        int count = 0;
        for(int j = 0;j<n;j++)
        {if(aux[j] == aux[i])
        {
            count++;
        }
        if(count>1)
        return aux[j];
        }
    }
    return -1;
}
int main() {
	
	    int n;
	    cin>>n;
	    int arr[n];
	    for(int i = 0;i<n;i++)
	    cin>>arr[i];
	    
	    
	        if(count(arr,n)!=-1)
	        
	            cout<<"Repeated Element is "<<count(arr,n);
	           else
	    cout<<"No element Repeated"<<endl;
	    
	    
	return 0;
}

Conclusion:

This is all I know about finding the first repeating element in the array. I show the code also if you have any doubts then please comment and in case of any mistake please correct us.