Repeating Element Index - C++ Solution

1. Introduction

In this post, we will explore a common problem in array processing: finding the minimum index of the first repeating element. This problem is key in understanding hash maps and efficient array traversal in C++. We aim to solve it in linear time with a single array traversal.

Problem

Given an integer array, the task is to find the minimum index at which an element repeats. If the array has no repeating elements, the output should be -1.

Examples:

- Input: [5, 6, 3, 4, 3, 6, 4]

Output: 1

- Input: [1, 2, 3, 4, 5, 6]

Output: -1

2. Solution Steps

1. Initialize an empty hash map to store the indices of elements.

2. Traverse the array, adding each element and its index to the hash map.

3. If an element is already in the hash map, return its stored index.

4. If the traversal is completed without finding a repeating element, return -1.

3. Code Program

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

// Function to find the minimum index of a repeating element
int findMinIndexOfRepeating(vector<int>& nums) {
    unordered_map<int, int> indexMap; // To store indices of elements

    for (int i = 0; i < nums.size(); ++i) {
        if (indexMap.find(nums[i]) != indexMap.end()) {
            return indexMap[nums[i]]; // Found a repeating element
        }
        indexMap[nums[i]] = i; // Store the index of the element
    }

    return -1; // No repeating element found
}

int main() {
    vector<int> nums = {5, 6, 3, 4, 3, 6, 4};
    cout << "Minimum index of repeating element: " << findMinIndexOfRepeating(nums) << endl;
    return 0;
}

Output:

Minimum index of repeating element: 1

Explanation:

The function findMinIndexOfRepeating uses a hash map to track the indices of elements. As it traverses the array, it checks if the current element is already in the hash map. If it is, the function returns the index at which this element first appeared. If no repeating element is found during the traversal, the function returns -1, indicating that there are no repeating elements in the array.