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[5] = {2, 3, 5, 3, 1};
    firstRepeat(arr,5);
}
 
OUTPUT:
First repeating element of an array is 3.

Method 2: Hashing Based Approach 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;
        }
        /* If not found, insert arr[i] in set */
        st.insert(arr[i]);
    }
    cout<<"There is no repeated element in an array!!";
}
int main()
{
    int arr[5] = {2, 3, 5, 3, 1};
    firstRepeat(arr,5);
}

OUTPUT:
First repeating element of an array is 3

Related Posts:

  1. Find Most Frequent Character of the String.
  2. Check Anagram Strings.
  3. Check Whether Given String is Palindromic Anagram or Not.
  4. Check Whether Given String is Panagram or Not.
  5. Find First Non-Repeating Character of the String.
  6. Find Most Frequent Element of the Array.
  7. Find Pair in an Array with Given Sum.
  8. Find Majority Element of an Array.
  9. Program to count occurrences of a particular element in an array.
  10. Program to search an element in an Array (Linear Search).
  11. Program to Rotate Array Elements by ‘D’ positions.
  12. Program to find most frequent element in an array.
  13. Program to find pair in an array with given sum.
  14. Program to find first repeating element of an array.
  15. Program to merge two sorted arrays.
  16. Program to find missing number in an array.
  17. Program to sort if array is sorted.
  18. Program to print Alternate Elements of an Array.
  19. Program to swap kth element from beginning to kth element from end in an Array.
  20. Program to print all possible subarrays of the given array.

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *