Hashing: Find the first repeating element and index in the array

Problem Statement:

You are given an array with repeated elements.

You need to find the first repeating element.

Example:

Input: arr = [4, 3, 5, 6, 5, 6]

Output: 5

Solution Explanation:

We will use hash set to solve the problem.

We will iterate through the array, if the element is not present in the hash set then insert into the set.

If the element is already present, then return the element

Time Complexity: O(n)
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <unordered_set>
using namespace std;

int solution(const vector<int>& arr) 
{
    unordered_set<int> s;

  	int minIndex = INT_MAX;

    for (int i = arr.size() - 1; i >= 0; i--) 
    {
        if (s.find(arr[i]) != s.end()) 
        {
            minIndex = min(minIndex, i);
        }

        s.insert(arr[i]);
    }
  
    return minIndex == INT_MAX? -1: minIndex;
}

int main()
{
    vector<int> arr = {4, 3, 5, 6, 5, 6};
    int index = solution(arr);
    if (index == -1)
        cout << "No repeating element!" << endl;
    else
        cout << "First repeating element is " << arr[index] << " index is = " <<index<<endl;
    return 0;
}

Output

First repeating element is 5 index is = 2