Find the minimum index of a repeating element in an array

By | March 17, 2022
Find the minimum index of a repeating element in an array

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 first occurrence is 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

Vamware
First repeating element is 3

People are also reading:

Author: Vinay Singh

I am a Full Stack Developer with a Bachelor's Degree in Computer Science, who also loves to write technical articles that can help fellow developers.

Leave a Reply

Your email address will not be published.