How to find the first repeating element in an array of integers

An array in C++ stores multiple values of the same data type in a single variable. We can also say it's a collection of similar items. These items of the same data types in an array are its elements. We can access these elements using the index of the array.

A pictorial representation of arrays is shown below:

The length of this array is 5.
The data type of values stored in this array is an integer.

Find the first repeating element

Given an array of $n$ integers, print the first repeating element from the array. There are many ways to solve this problem, but we'll opt for the most efficient one:

Method 1: Use a nested loop, the outer loop will pick an element one by one, and the inner loop will check if the element is repeated. It will break the loop and print the element.

Method 2: Use hashing, traverse the given array from right to left, and if the element is already in the hash set, update the minimum index. Otherwise, add that element to the hash set.

Proposed solution

Let's pick the first method to solve this problem:

Steps

Use a nested loop, and let the outer loop pick an element one by one.
The inner loop will check the occurrence of elements one by one.
If the repeated element is found, break the loop and print the element. If the element is not found, it will print No repeating element is found.

Code example

Let's look at the example below:

#include <iostream>
using namespace std;
int main() {
    int arr[] = {1, 2, 3, 3, 3, 6, 6};
    int n = sizeof(arr) / sizeof(*arr);
    for(int i=0;i<n;i++) // select an element
    {
      // j is intialized with i+1, because 'j = i' is the element itself to compare
      for(int j=i+1;j<n;j++) //traverse ahead and check for duplicate
      {
        // Comparing the element with whole array
        if(arr[i]==arr[j])
          {
            cout<<arr[i];
            return 0;
          }
      }
    }
    // If none of the element is repeating
    
  cout<<"No repeating integer found\n";
  
  return 0;
}

Explanation

In the code above:

Line 6: Intiliaze an array with repeating elements.
Line 7: Find the length of the array and store in the variable n.
Line 9: An outer for loop that iterates through each element of the array.
Line 12: An outer for loop that iterates through the whole array for every single element.
Line 16: Compare the ith element with the whole array.
Lines 18-19: Print the first repeating element and stop the iteration with return 0.
Line 25: Print "No repeating integer found\n" if the array have no repeating element.

Complexity

The time complexity is $O(n^2)$ .