# First Repeating Element in an Array

First Repeating Element in an Array” is an important and one of the favourite technical interview problems based on array data structure. Here, we are given an array of ‘n’ elements and our task is to find the first repeating element in an array.

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

#### Example (First Repeating Element in an Array):

```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 Approach to find first repeating Element in an Array

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(n2), where ‘n’ is size of an array.

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

```/* C++ Program to find first repeating element in an Array */
#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 BasedApproach to find first repeating element in an array

The steps required to find first repeating element in an 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:

```/* C++ Program to find first repeating element in an array */
#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: