Find the first repeating element in an array

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.

Algorithm working

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;
}
Try It

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.

Algorithm working

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;
}
Try It

 


Next > < Prev
Scroll to Top