Find the first repeating element in an array of integers

Problem Statement

Find the first repeating element in an array of integers problem states that you are given an array of integer. It asks to find out the first repeating element from the array and print that number.

Example

arr[] = {2,6,9,3,1,9,1}

9

Explanation: In the given array there are two numbers which is repeating but the first repeating is 9.

arr[] = {1,4,7,0,2,5}

No repeating number.

Explanation: In the given array there is no repeating number.

Algorithm to find a first repeating character

1. Set flag to -1.
2. Declare a Set.
3. Start traversing the array from the right to left.
    1. If the number is repeating then update the value of flag to the index of the current array element.
    2. Else, insert the each array’s element into the declared set.
4. Check if flag value is still -1, then we have found no repeating element.
5. Else print flag index position of array.

Explanation

We have given an array of integers, we have asked to find if there is any repeating element then print, but the condition is that number in the array should be the first repeating element. The number which is repeating first in the array will be the required answer, that is, why we are traversing it from right to left. We will be using a set. Set has the feature to not store the common elements in Set. So when we found one repeating in the array we just simply get its index and afterward print that index’s element.

We will declare a set, start traversing from the right of the array, we will check if set already contains the value of current array element if it contains then get its index and update the value of the flag to that index, this flag value we will be using it as an index and later we will be printing that value.

Before that, we should insert all the values of the array while traversing, so when we get a similar value, we will be storing that element’s index. Though we are traversing the array from the right, if we found any element in the right which is repeating in the left, that means it is the first repeating element. We are updating the flag value because later on, we will be checking if the flag value is still -1 or it is updated. If it is still -1, it means we have found no repeating element, if it is updated then we will print the flag’s index value of an array.

Code

C++ code to find a first repeating character

#include<bits/stdc++.h>

using namespace std;

void getFirstRepeatedElement(int arr[], int n)
{
    int Flag = -1;

    unordered_set<int> SET;

    for (int i = n - 1; i >= 0; i--)
    {
        if (SET.find(arr[i]) != SET.end())
            Flag = i;

        else
            SET.insert(arr[i]);
    }
    if (Flag!= -1)
        cout << "The first repeating element is " << arr[Flag];
    else
        cout << "There are no repeating elements";
}
int main()
{
    int arr[] = {2,6,9,3,1,9,1};

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

The first repeating element is 9

Java Code to find a first repeating character

import java.util.HashSet;

class FirstRepeatingElement
{
    public static void getFirstRepeatedElement (int arr[])
    {
        int Flag = -1;

        HashSet<Integer> SET = new HashSet<>();

        for (int i=arr.length-1; i>=0; i--)
        {
            if (SET.contains(arr[i]))
                Flag = i;

            else
                SET.add(arr[i]);
        }
        if (Flag!= -1)
            System.out.println("First repeating element is " + arr[Flag]);
        else
            System.out.println("No repeated element");
    }
    public static void main (String[] args)
    {
        int arr[] = {2,6,9,3,1,9,1};
        getFirstRepeatedElement(arr);
    }
}

First repeating element is 9

Complexity Analysis

Time Complexity

O(n) where “n” is the number of elements in the array. Since we are using a HashSet, we can perform insertion and search in O(1) operations.

Space Complexity

O(n) where “n” is the number of elements in the array.