Find Minimum Index of Repeating Element in Array

Given an array of integers. The task is to find the Minimum index of repeating element in an array in linear time and in a single traversal of the array.

Examples:

Input : {5, 6, 2, 1, 6, 1, 2}
Output : Minimum index of repeating element is 1

Input : {1, 2, 5, 6, 7}
Output : Invalid input

Naive Approach:
Consider each element arr[i] present in the array and search in the sub-array arr[i+1…n-1]. Return its index as a duplicate is found. Its complexity is O(n^2)

Efficient Approach:
Use hashing to perform in linear time. Traverse array from right to left. If the element is seen for first time insert it into set else update minimum index with element’s index. Finally return the minimum index.

#include <iostream>
#include <unordered_set>
using namespace std;

// Function to find minimum index of repeating element
int findMinIndex(int arr[], int n) {
    int minIndex = n;

    // Create an empty set to store array elements
    unordered_set<int> set;

    // Traverse array from right to left
    for (int i = n - 1; i >= 0; i--) {
        // If the element is seen before, update minimum index
        if (set.find(arr[i]) != set.end()) {
            minIndex = i;
        } else {
            // If the element is seen for the first time, insert it into the set
            set.insert(arr[i]);
        }
    }

    // Return minimum index
    return minIndex;
}

// Main function
int main() {
    int arr[] = {5, 6, 3, 4, 3, 6, 4};
    // int arr[] = {1, 2, 3, 4, 5, 6}; // Uncomment for different input

    int n = sizeof(arr) / sizeof(arr[0]);

    int minIndex = findMinIndex(arr, n);

    if (minIndex != n) {
        cout << "Minimum index of repeating element is " << minIndex;
    } else {
        cout << "Invalid Input";
    }

    return 0;
}

Output:

Minimum index of repeating element is 1

Time Complexity: O(n)