Find the minimum index of a repeating element in an array

Posted in

Find the minimum index of a repeating element in an array

Vinay Khatri
Last updated on September 28, 2022

    Problem

    Given an array of integers, find the first repeating element in it. We need to find the element that occurs more than once and whose index of the first occurrence is the smallest.

    Sample Input

    [1, 2, 2, 1]

    Sample Output

    1

    Explanation

    1 is the first one occurring twice.

    Approach

    We can use sets to solve this efficiently. We can traverse the given array from right to left and update the minimum index whenever we find an element that has already been encountered. This approach takes O(N) time and O(N) auxiliary space.

    C++ Programming

    #include<bits/stdc++.h>
    using namespace std;
    
    void solve(int arr[], int n)
    {
       int min_index = -1;
    
       set<int> s;
    
       for (int i = n - 1; i >= 0; i--)
       {
           // If element is already in hash set
           if (s.find(arr[i]) != s.end())
               min_index = i;
    
           else // Else add element to hash set
               s.insert(arr[i]);
       }
    
      
       if (min_index != -1)
           cout << "First repeating element is " << arr[min_index];
       else
           cout << "There are no repeating numbers";
    }
    
    int main()
    {
       int arr[] = {1, 2, 3, 4, 3};
    
       int n = sizeof(arr) / sizeof(arr[0]);
       solve(arr, n);
    }
    

    Output

    First repeating element is 3

    Python Programming

    def solve(arr, n):
        Min = -1
     
        vis = dict()
     
        for i in range(n - 1, -1, -1):
         
            if arr[i] in vis.keys():
                Min = i
            else: 
                vis[arr[i]] = 1
         
        if (Min != -1):
            print("The first repeating element is",
                                          arr[Min])
        else:
            print("There are no repeating elements")
     
    arr = [1, 2, 3, 4, 3]
     
    n = len(arr)
    solve(arr, n)
     

    Output

    First repeating element is 3

    Java Programming

    import java.util.*;
    
    class Main
    {
       static void solve(int arr[])
       {
           int min_index = -1;
    
           HashSet<Integer> s = new HashSet<>();
    
           for (int i=arr.length-1; i>=0; i--)
           {
               // If element is already in set
               if (s.contains(arr[i]))
                   min_index = i;
    
               else // Else add element to set
                   s.add(arr[i]);
           }
    
           if (min_index != -1)
           System.out.println("First repeating element is " + arr[min_index]);
           else
           System.out.println("No repeating elements");
       }
    
       public static void main (String[] args)
       {
           int arr[] = {1, 2, 3, 4, 3};
           solve(arr);
       }
    }

    Output

    First repeating element is 3
    

    People are also reading:

    Tags:
    array

    Leave a Comment on this Post

    0 Comments