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

• WAP to Print Square Using * Character
• Diameter of a Binary Tree
• Subset Sum Problem
• Maximum size square sub-matrices with all 1’s
• Find K-th Smallest Element in BST
• Check if directed graph is connected
• Quicksort using Dutch National Flag Algorithm
• Problems solved using partitioning logic of Quick-sort
• Print a two-dimensional view of a Binary Tree
• Sort binary array in linear time