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

Table of Contents

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.