First Repeating Element

Last updated: 29th Aug, 2020

  

Problem Statment

An array arr[] of size N is given .
Find the first repeating element in an array of integers,i.e.,an element that occurs more than once and whose index of first occurrence is smallest.

Constraints: 1 <= N <= 10^6 0 <= A <= 10^6

Input Format
[1,2,3,4,3,1,6]

Output Format
element: 3
index: 2

Approach:

The program is solved using function
1.first_repeating- function is declared with two arguments( arr : a array which stores the elements , n: size of the array)
 The whole logic behind the program is that :
2.Min is initialized to its minimum value (-1)
3.A dictionary is declared
4.A loop will transverse through the array from right to left
5.If the element is present in the dictionary then
6.Update the Min
7.If the element is not present ,then add the element in the dictionary
8.Print the element with its index number.

Python Code

  def first_repeating(n,arr):
 #initialize with the minimum index possible
     Min = -1
    #create a empty dictionary
     newSet = dict()
     # tranversing the array elments from end
     for x in range(n - 1, -1, -1):
      #check if the element is already present in the dictionary
      #then update min
        if arr[x] in newSet.keys(): 
          Min = x 
          #if element is not present
          #add element in the dictionary
        else: 
          newSet[arr[x]] = 1
                      
          #print the minimum index of repeating element
          if (Min != -1): 
            print("The first repeating element is",arr[Min]) 
          else: 
            print("There are no repeating elements") 
                  
  #Drivers code
                  
  arr = [10, 5, 3, 4, 3, 5, 6] 
                    
  n = len(arr)
  print(first_repeating(n,arr))