# 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:

- With count function
- By sorting the array
- 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).

## Leave a Reply