# Find the first repeating element in an array

0
983

## Find the first repeating element in the given array.

Repeating elements are elements which comes more than once.Â (Array may contain duplicates)

### Example

Input array

Repeating elements are 4, 7
First repeating element is 4.

## Algorithm 1

Time Complexity:O(N^2)

Run two loops such that select every element from the array and traverse ahead and check for duplicate in the array.
a)Â Â Â  If found print as First repeating integer.
b)Â Â Â  Else print No repeating integer found.
As we are running two loops order is O(N^2) N is size of array.

## C++ Program

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

int main()
{

int arr[] = {6, 10, 5, 4, 9, 120, 4, 6, 10}; // array
int N = sizeof(arr)/sizeof(arr[0]); // size of array

for(int i=0;i<N;i++) // select an element
for(int j=i+1;j<N;j++) //traverse ahead and check for duplicate
if(arr[i] == arr[j])
{
cout << "First repeating integer is "<<arr[i];
return 0;
}

cout<<"No repeating integer found\n";

return 0;
}``````

## Algorithm 2

Time Complexity:O(N)

This is like Hashing, we store the count of the number and index along with array element.

Step 1 :
Create a vector M such that it acts like map function which contains the index of the array element with the pair of count and index.
a)Â Â Â  Here index is the minimum index of the element which is repeated.
b)Â Â Â  Count is number of times it is repeated.

Step 2 : Create an iterator to traverse in the map.

Step 3 : Run a loop such that we select every element of the array from left. And find the element in the array, if already present update its count.

Step 4 : If element is coming for the first time, then add it to the map.
a)Â Â Â  Â Count equal to 1
b)Â Â Â  Occurrence at index i, if you are at i.

Step 5 : Get the minimum index by traversing into the map.
a)Â Â Â  Â Initialize the min_index to INT_MAX
b)Â Â Â  Traverse the map to find min_index so, find second of Map, then second of the second to get the index.
c)Â Â Â  Use Inbuilt min function to compare the min_index.
d)Â Â Â  Finally store it.

Step 6 : Finally, if min_index not equal to INT_MAX, print it as the first repeating integer because there is some integer which is repeted. Else Print no repeating integer.

## C++ Program

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

int main()
{

int arr[] = {6, 10, 5, 4, 9, 120, 4, 6, 10}; // array
int N = sizeof(arr)/sizeof(arr[0]); // size of array

map<int,pair<int,int> > M; //map the index of the array element with the pair of count and index that implies the element with the minimum index which is repeated
map<int,pair<int,int> > ::iterator it;//iterator to traverse the map
for(int i=0; i<N; i++)//select an element
{
it = M.find(arr[i]); //find the element

if(it != M.end())//if element already present update its count
{
pair<int,pair<int,int> > temp = (*it);
pair<int,int> p = temp.second;
p.second++;
M.erase(it);
M.insert(make_pair(arr[i],p));
}

else //if element came for the first time then add it into the map with count 1 and occurence at i
M.insert(make_pair(arr[i],make_pair(i,1)));
}

int min_index = INT_MAX; //obtaint the minimum index
for(it = M.begin(); it != M.end(); it++) //traverse the entire map
{
pair<int,pair<int,int> > temp = (*it);
pair<int,int> p = temp.second;
if(p.second > 1)
min_index = min(min_index,p.first);	//minimum index of the element that is repeating
}

if(min_index != INT_MAX)
cout<<"First repeating element that is repeated is "<<arr[min_index];
else
cout<<"No repeating integer found\n";

return 0;
}``````

If you have come this far, it means that you liked what you are reading. I am a software developer (graduated from BITS Pilani). I love writing technical articles on programming and data structures.