# First Repeating Element of an Array

First Repeating Element of an Array” is an important and one of the favorite technical interview problems. Here, we are given an array of ‘n’ element and Our task is to find the first element which repeats itself.

If all the elements of the array are unique, simply return, -1.

Example:

```INPUT:
Arr[] = {23, 45, 46, 11, 45, 22, 46}
OUTPUT:
45 is the first repeating element of an array```

There are multiple methods to find first repeating element of an array. Some of them are:

METHOD 1: Brute-Force

Simply use two nested loops. For every element of the array, run the inner loop from ‘current_index + 1’ to (n-1). If at any point we get duplicate element, return that element.

If all the elements of the array are unique, simply return -1.

Because of two nested loops, the time complexity of this solution is O(n^2), where ‘n’ is size of an array.

C++ Program to find first repeating element in an array is as follows:

```#include<bits/stdc++.h>
using namespace std;
/* function to find first repeating element */
void firstRepeat(int arr[],int n)
{
int i,j;
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(arr[i] == arr[j])
{
cout<<"First repeating element of an array is "<<arr[i];
return;
}
}
}
cout<<"There is no repeated element in an array";
}
int main()
{
int arr = {2, 3, 5, 3, 1};
firstRepeat(arr,5);
}

```
```OUTPUT:
First repeating element of an array is 3.```

Method 2: Hashing Based

The steps required to find the first repeating element of the array is as follows:

1. Create an empty set.
2. For every element of the array, we need to check whether it is already present in set or not. If already present, then return that element.
3. Else, insert that element in the set.
4. If all the elements of the array are unique, simply return -1.

The time complexity of this solution is O(nlogn), where ‘n’ is size of array and ‘logn’ is for inserting and finding in set.

C++ Program to find first repeating element in an array is as follows:

```#include<bits/stdc++.h>
using namespace std;
/* function to find first repeating element of an array */
void firstRepeat(int arr[],int n)
{
int i,j;
/* Declare set*/
set<int> st;
for(i=0;i<n;i++)
{
/* find current element in a set */
if(st.find(arr[i]) != st.end())
{
/* If found, it will be first repeating element and return */
cout<<"The first repeating element is "<<arr[i]<<"\n";
return;
}
st.insert(arr[i]);
}
cout<<"There is no repeated element in an array!!";
}
int main()
{
int arr = {2, 3, 5, 3, 1};
firstRepeat(arr,5);
}

```
```OUTPUT:
First repeating element of an array is 3```

Related Posts: