First Repeating Element of an Array

First Repeating Element of an Array” is an important and one of the favorite technical interview problems. Here, we are given an array of ‘n’ element and Our task is to find the first element which repeats itself. 

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

Example:

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

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

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

#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

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

#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. Program to merge two sorted arrays.
  2. Program to find missing number in an array.
  3. Program to sort if array is sorted.
  4. Program to print Alternate Elements of an Array.
  5. Program to swap kth element from beginning to kth element from end in an Array.
  6. Program to print all possible subarrays of the given array.
  7. Program to print kth smallest and kth largest element of an Array.
  8. Program to find equilibrium index of an Array.
  9. Program to find majority element of an Array.
  10. Program to find mean of the Array.
  11. Program to sort an Array of 0s and 1s.
  12. Program to Reverse an Array.
  13. Program to count number of odd numbers and even numbers in an array.
  14. Program to find absolute difference between sum of odd index elements and even index elements.
  15. Program to find smallest and largest element of the array.
  16. Program to count occurrences of a particular element in an array.
  17. Program to search an element in an Array (Linear Search).
  18. Program to Rotate Array Elements by ‘D’ positions.
  19. Program to find most frequent element in an array.
  20. Program to find pair in an array with given sum.

You may also like...

Leave a Reply

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