Find the first repeating element in an array of integers in Python

In this tutorial, we will learn how to find the first repeating element in an array in Python.

Considering an array of N elements, we need to find the first element which has more than one occurrence.

For example:

Input: arr = [1, 3, 4, 5, 5, 3, 4, 6]

Output: 3 (Because 3 is the first repeating element in the array)

Program to find the first repeating element in the array

We can do this in multiple ways:

1. With count function
2. By sorting the array
3. With the help of dictionary

Using count function

Traversing the array linearly and using the count() function to check for the repeating element of the array. The count function in python takes one parameter i.e the element and returns the count of the element in the array. As soon as we find the element which has more than one occurrence we break the loop and print the element.

Following is the code snippet of the above method in Python

#Program to find the first repeating element in array

arr = [1, 3, 4, 5, 5, 3, 4, 6]

repeat_ele = -1

for element in arr:
    c = arr.count(element) # count the occurrence of element
    if c > 1:
        repeat_ele = element #found the first repeating element
        break;
        
# if repeat_ele is -1 means their are no repeating elements
if repeat_ele == -1:
    print("There are no repeating elements in array")
else:
    print("The first repeating element is",repeat_ele)

Output:

The first repeating element is 3.

 

By sorting the array

Another way is to sort the array and linearly check if the two adjacent elements in the array are equal or not. If we elements equal we break the loop and print the element.

Following is the code for the above approach in python.

#Program to find the first repeating element in array

arr = [1, 3, 4, 5, 5, 3, 4, 6]

repeat_ele = -1

#sorting the array
arr.sort()

for i in range(len(arr)-1):
    #check if adjacent elements are equal or not
    if arr[i]==arr[i+1]:
        repeat_ele = arr[i]
        break
        
# if repeat_ele is -1 means their are no repeating elements
if repeat_ele == -1:
    print("There are no repeating elements in array")
else:
    print("The first repeating element is",repeat_ele)

Output:

The first repeating element is 3.

 

Using Python dictionary

The efficient way to find the first repeating element is by using a dictionary in python.

In this method, we initialize the repeating element index to -1 and traverse the array from right to left, while traversing the array we store the elements in the dictionary and update the index value to the current element index. Once the complete array is traversed the index contains the first repeating element.

def repeat_element(arr, n): 
  
    # Initialize index of first repeating element 
    index = -1
    
    # creating an empty dictionary
    mydict = {} 
  
    # Traverse the input array from right to left 
    for i in range(n - 1, -1, -1): 
      
        # If element is in dictionary, 
        # update the index value
        if arr[i] in mydict.keys(): 
            index = i 
        else: 
            mydict[arr[i]] = 1  # add the element to the dictionary
      
    return index
  
# Driver Code 

arr = [1, 3, 4, 5, 5, 3, 4, 6] 
  
n = len(arr) 

x = repeat_element(arr, n) 

# if x is -1 means there are no repeating elements
if x == -1:
    print("There are no repeating elements in array")
else:
    print("The first repeating element is",arr[x])

Output:

The first repeating element is 3.

The time complexity of the above program is O(n).