Find the first repeating element in array of integers.
For example :
For example :
Input : Input: array[] = {10, 7, 8, 1, 8, 7, 6} Output: 7 [7 is the first element actually repeats]
Solution
A simple solution will be to use two loops. The outer loop will iterate through the loop and the inner loop will check if the element is repeated or not but the time complexity of this solution will be o(n^2).
Another solution will be to create another array and sort it. Pick an element from an original array and find the element in the sorted array using binary search but the time complexity of this solution will be o(n^logn).
Can we do better?
Yes, we can iterate from right to left and use HashSet to keep track of the minimum index.
- Initialize minimum index with -1
- Iterate over the input array from right to left
- If the element is already present in HashSet, then update the minimum index else add an element to the set
- Once we are done with iteration, we will get minimum index in the end
Program to find the first repeating element in an array of integers
/* Java program to find first repeating element in arr[] */ import java.util.*; public class FirstRepatingElementMain { // This function prints the first repeating element in arr[] static int getFirstRepeatingElementArray(int array[]) { // Initialize index of first repeating element int minimumIndex = -1; // Creates an empty hashset HashSet<Integer> set = new HashSet<>(); // Iterate over the input array from right to left for (int i=array.length-1; i>=0; i--) { // If set contains the element, update minimum index if (set.contains(array[i])) minimumIndex = i; else // Else add element to hash set set.add(array[i]); } return minimumIndex; } public static void main (String[] args) throws java.lang.Exception { int array[] = {10, 7, 8, 1, 8, 7, 6}; int min=getFirstRepeatingElementArray(array); // Print the result if (min != -1) System.out.println("The first repeating element in array is " + array[min]); else System.out.println("There are no repeating elements"); } }
When you run the above program, you will get the below output:
The first repeating element in array is 7
The time complexity of this solution is O(n) and space complexity is also O(n).