Home » Technical Interview Questions » Array Interview Questions » First Repeating Element

First Repeating Element


Reading Time - 2 mins

We have given an array that contains n integers. We have to find the first repeating element in the given array. If there is no repeated element then print “No repeating integer found”.

Note: Repeating elements are those elements that come more than once. (Array may contain duplicates)

Example

Input

6

1 2 3 1 4 2

Output

1

Approach 1 for First Repeating Element

Run two loops such that select every element from the array and traverse ahead and check for a 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 the size of the array.

C++ Program for First Repeating Element

#include <bits/stdc++.h>
using namespace std;
int main()
{
  
  int n;
  cin>>n;
  int arr[n];
  for(int i=0;i<n;i++)
  {
      cin>>arr[i];
  }
  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<<arr[i];
            return 0;
          }
  cout<<"No repeating integer found\n";
  return 0;
}
5
10 3 5 3 2
3

Complexity Analysis for First Repeating Element

Time Complexity: O(N^2) where N is the size of the array. Here we pick one element and check it whether it is equal to other elements that are present next to that element.

Space Complexity: O(1) because we don’t use any auxiliary space here.

Approach 2 for First Repeating Element

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

READ  Palindrome Permutation

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 the number of times it is repeated.

Step 2: Create an iterator to traverse on 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 the element is coming for the first time, then add it to the map.
a)     Count equal to 1
b)    An 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 the 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 repeated. Else Print no repeating integer.

C++ Program

#include <bits/stdc++.h>
using namespace std;
int main()
{
  
  int n;
  cin>>n;
  int arr[n];
  for(int i=0;i<n;i++)
  {
      cin>>arr[i];
  }
  unordered_map<int,pair<int,int> > M;
  unordered_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<<arr[min_index];
  else  
  cout<<"No repeating integer found\n";
  return 0;
}
7
1 3 5 30 2 1 3
1
Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions