Find the first repeating element in an array of integers
Last Updated :
06 Jul, 2023
Given an array of integers arr[], The task is to find the index of first repeating element in it i.e. the element that occurs more than once and whose index of the first occurrence is the smallest.
Examples:
Input: arr[] = {10, 5, 3, 4, 3, 5, 6}
Output: 5
Explanation: 5 is the first element that repeats
Input: arr[] = {6, 10, 5, 4, 9, 120, 4, 6, 10}
Output: 6
Explanation: 6 is the first element that repeats
Naive Approach: Below is the idea to solve the problem
Run two nested loops, the outer loop picks an element one by one, and the inner loop checks whether the element is repeated or not. Once a repeating element is found, break the loops and print the element.
C++
#include <bits/stdc++.h>
using namespace std;
int firstRepeatingElement(int arr[], int n)
{
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (arr[i] == arr[j]) {
return i;
}
}
}
return -1;
}
int main()
{
int arr[] = { 10, 5, 3, 4, 3, 5, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
int index = firstRepeatingElement(arr, n);
if (index == -1) {
cout << "No repeating element found!" << endl;
}
else {
cout << "First repeating element is " << arr[index]
<< endl;
}
return 0;
}
|
Java
import java.util.*;
public class GFG {
public static int firstRepeatingElement(int[] arr, int n) {
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (arr[i] == arr[j]) {
return i;
}
}
}
return -1;
}
public static void main(String[] args) {
int[] arr = { 10, 5, 3, 4, 3, 5, 6 };
int n = arr.length;
int index = firstRepeatingElement(arr, n);
if (index == -1) {
System.out.println("No repeating element found!");
}
else {
System.out.println("First repeating element is " + arr[index]);
}
}
}
|
Python3
def firstRepeatingElement(arr, n):
for i in range(n):
for j in range(i+1, n):
if arr[i] == arr[j]:
return i
return -1
if __name__ == '__main__':
arr = [10, 5, 3, 4, 3, 5, 6]
n = len(arr)
index = firstRepeatingElement(arr, n)
if index == -1:
print("No repeating element found!")
else:
print("First repeating element is", arr[index])
|
C#
using System;
public class Program
{
public static void Main()
{
int[] arr = { 10, 5, 3, 4, 3, 5, 6 };
int n = arr.Length;
int minIndex = n;
int minValue = int.MaxValue;
var dict = new System.Collections.Generic.Dictionary<int, int>();
for (int i = 0; i < n; i++)
{
int val = arr[i];
if (!dict.ContainsKey(val))
{
dict[val] = i;
}
else
{
int index = dict[val];
if (index < minIndex || (index == minIndex && val < minValue))
{
minIndex = index;
minValue = val;
}
}
}
if (minIndex == n)
{
Console.WriteLine("No repeating element found!");
}
else
{
Console.WriteLine("First repeating element is " + minValue + " at index " + minIndex);
}
}
}
|
Javascript
function firstRepeatingElement(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
if (arr[i] === arr[j]) {
return i;
}
}
}
return -1;
}
const arr = [10, 5, 3, 4, 3, 5, 6];
const index = firstRepeatingElement(arr);
if (index === -1) {
console.log("No repeating element found!");
} else {
console.log("First repeating element is", arr[index]);
}
|
Output
First repeating element is 5
Time Complexity: O(N2)
Auxiliary Space: O(1)
Find the first repeating element in an array of integers using sorting:
Below is the idea to solve the problem.
Store the elements of arr[] in a duplicate array temp[], sort temp[] and traverse arr[] from 0 to N – 1, Simultaneously check the count of this element in temp[] and if the current element arr[i] has more than one occurrence then return arr[i].
Follow the steps below to Implement the idea:
- Copy the given array to an auxiliary array temp[] and sort temp array.
- Traverse the input array arr[] from 0 to N – 1.
- If no repeating element is found print “No Repeating Number Found”.
Time complexity: O(NlogN).
Auxiliary Space: O(N)
Find the first repeating element in an array of integers using Hashset
Below is the idea to solve the problem
The idea is to traverse the given array arr[] from right to left and update the minimum index whenever, an already visited element has been found. To check if the element was already visited Hashset can be used.
Follow the steps below to implement the idea:
- Initialize an empty Hashset myset and a variable min with -1.
- Run a for loop for each index of array arr[] from N – 1 to 0.
- If the current element is present in myset then update min with i.
- Else insert arr[i] in myset.
- Return min.
Below is the implementation of the above approach.
C++
#include <bits/stdc++.h>
using namespace std;
void printFirstRepeating(int arr[], int n)
{
int min = -1;
set<int> myset;
for (int i = n - 1; i >= 0; i--) {
if (myset.find(arr[i]) != myset.end())
min = i;
else
myset.insert(arr[i]);
}
if (min != -1)
cout << "The first repeating element is "
<< arr[min];
else
cout << "There are no repeating elements";
}
int main()
{
int arr[] = { 10, 5, 3, 4, 3, 5, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
printFirstRepeating(arr, n);
}
|
Java
import java.util.*;
class Main {
static void printFirstRepeating(int arr[])
{
int min = -1;
HashSet<Integer> set = new HashSet<>();
for (int i = arr.length - 1; i >= 0; i--) {
if (set.contains(arr[i]))
min = i;
else
set.add(arr[i]);
}
if (min != -1)
System.out.println(
"The first repeating element is "
+ arr[min]);
else
System.out.println(
"There are no repeating elements");
}
public static void main(String[] args)
throws java.lang.Exception
{
int arr[] = { 10, 5, 3, 4, 3, 5, 6 };
printFirstRepeating(arr);
}
}
|
Python3
def printFirstRepeating(arr, n):
Min = -1
myset = dict()
for i in range(n - 1, -1, -1):
if arr[i] in myset.keys():
Min = i
else:
myset[arr[i]] = 1
if (Min != -1):
print("The first repeating element is",
arr[Min])
else:
print("There are no repeating elements")
arr = [10, 5, 3, 4, 3, 5, 6]
n = len(arr)
printFirstRepeating(arr, n)
|
C#
using System;
using System.Collections.Generic;
public class GFG {
public static void printFirstRepeating(int[] arr)
{
int min = -1;
HashSet<int> set = new HashSet<int>();
for (int i = arr.Length - 1; i >= 0; i--) {
if (set.Contains(arr[i])) {
min = i;
}
else
{
set.Add(arr[i]);
}
}
if (min != -1) {
Console.WriteLine(
"The first repeating element is "
+ arr[min]);
}
else {
Console.WriteLine(
"There are no repeating elements");
}
}
public static void Main(string[] args)
{
int[] arr = new int[] { 10, 5, 3, 4, 3, 5, 6 };
printFirstRepeating(arr);
}
}
|
Javascript
<script>
function printFirstRepeating(arr)
{
let min = -1;
let set = new Set();
for(let i = arr.length - 1; i >= 0; i--)
{
if (set.has(arr[i]))
min = i;
else
set.add(arr[i]);
}
if (min != -1)
document.write("The first repeating element is " +
arr[min]);
else
document.write("There are no repeating elements");
}
let arr = [ 10, 5, 3, 4, 3, 5, 6 ];
printFirstRepeating(arr);
</script>
|
Output
The first repeating element is 5
Time Complexity: O(n).
Auxiliary Space: O(n).
Thanks to Mohammad Shahid for suggesting this solution.
Find the first repeating element in an array of integers using Hashing
The idea is to use Hash array to store the occurrence of elements. Then traverse the array from left to right and return the first element with occurrence more than 1.
Follow the below steps to implement the idea:
- Initialize variables k with 0, max with -1 and min with max + 1 and iterate over all values of arr[] to store the largest value in max.
- Initialize a Hash arrays a[] and b[] of size max + 1.
- Run a for loop from 0 to N – 1
- If a[arr[i]] is 0 put i+1 in place of a[arr[i]].
- Else assign 1 to b[arrr[i]] and k.
- If k is 0 print “No repeating element found”.
- Else iterate from 0 to max
- If a[i] is not zero and b[i] is not zero and min is greater than a[i] then update min a[i].
- Print min.
Below is the Implementation of above approach
C++
#include <bits/stdc++.h>
using namespace std;
void printFirstRepeating(int arr[], int n)
{
int k = 0;
int max = n;
for (int i = 0; i < n; i++)
if (max < arr[i])
max = arr[i];
int a[max + 1] = {};
int b[max + 1] = {};
for (int i = 0; i < n; i++) {
if (a[arr[i]]) {
b[arr[i]] = 1;
k = 1;
continue;
}
else
a[arr[i]] = i + 1;
}
if (k == 0)
cout << "No repeating element found" << endl;
else {
int min = max + 1;
for (int i = 0; i < max + 1; i++)
if (a[i] && min > a[i] && b[i])
min = a[i];
cout << arr[min - 1];
}
cout << endl;
}
int main()
{
int arr[] = { 10, 5, 3, 4, 3, 5, 6 };
int N = sizeof(arr) / sizeof(arr[0]);
printFirstRepeating(arr, N);
}
|
Java
public class GFG {
static void printFirstRepeating(int[] arr, int n)
{
int k = 0;
int max = n;
for (int i = 0; i < n; i++)
if (max < arr[i])
max = arr[i];
int[] a = new int[max + 1];
int[] b = new int[max + 1];
for (int i = 0; i < n; i++) {
if (a[arr[i]] != 0) {
b[arr[i]] = 1;
k = 1;
continue;
}
else
a[arr[i]] = i + 1;
}
if (k == 0)
System.out.println(
"No repeating element found");
else {
int min = max + 1;
for (int i = 0; i < max + 1; i++)
if (a[i] != 0 && min > a[i] && b[i] != 0)
min = a[i];
System.out.print(arr[min - 1]);
}
System.out.println();
}
public static void main(String[] args)
{
int[] arr = { 10, 5, 3, 4, 3, 5, 6 };
int N = arr.length;
printFirstRepeating(arr, N);
}
}
|
Python3
def printFirstRepeating(arr, n):
k = 0
max = n
for i in range(n):
if (max < arr[i]):
max = arr[i]
a = [0 for i in range(max + 1)]
b = [0 for i in range(max + 1)]
for i in range(n):
if (a[arr[i]]):
b[arr[i]] = 1
k = 1
continue
else:
a[arr[i]] = i+1
if (k == 0):
print("No repeating element found")
else:
min = max + 1
for i in range(max + 1):
if (a[i] and (min > (a[i])) and b[i]):
min = a[i]
print(arr[min-1])
arr = [10, 5, 3, 4, 3, 5, 6]
N = len(arr)
printFirstRepeating(arr, N)
|
C#
using System;
class GFG {
static void printFirstRepeating(int[] arr, int n)
{
int k = 0;
int max = n;
for (int i = 0; i < n; i++)
if (max < arr[i])
max = arr[i];
int[] a = new int[max + 1];
int[] b = new int[max + 1];
for (int i = 0; i < n; i++) {
if (a[arr[i]] != 0) {
b[arr[i]] = 1;
k = 1;
continue;
}
else
a[arr[i]] = i + 1;
}
if (k == 0)
Console.WriteLine("No repeating element found");
else {
int min = max + 1;
for (int i = 0; i < max + 1; i++)
if ((a[i] != 0) && min > a[i]
&& (b[i] != 0))
min = a[i];
Console.Write(arr[min - 1]);
}
Console.WriteLine();
}
static void Main()
{
int[] arr = { 10, 5, 3, 4, 3, 5, 6 };
int N = arr.Length;
printFirstRepeating(arr, N);
}
}
|
Javascript
<script>
function printFirstRepeating(arr , n) {
var k = 0;
var max = n;
for (i = 0; i < n; i++)
if (max < arr[i])
max = arr[i];
var a = Array(max + 1).fill(0);
var b = Array(max + 1).fill(0);
for (var i = 0; i < n; i++) {
if (a[arr[i]] != 0) {
b[arr[i]] = 1;
k = 1;
continue;
} else
a[arr[i]] = i+1;
}
if (k == 0)
document.write("No repeating element found");
else {
var min = max + 1;
for (i = 0; i < max + 1; i++)
if (a[i] != 0 && min > a[i] && b[i] != 0)
min = a[i];
document.write(arr[min-1]);
}
document.write("<br/>");
}
var arr = [ 10, 5, 3, 4, 3, 5, 6 ];
var N = arr.length;
printFirstRepeating(arr, N);
</script>
|
Time Complexity: O(N).
Auxiliary Space: O(N).
Another approach using single hash array
Follow the below steps to implement the idea:
- Initialize a variable max to -1 to keep track of the maximum value in the array.
- Iterate over all values of arr[] to store the largest value in max.
- Declare an integer array hash of size max+1 and initialize all its elements to 0. This array will be used as a hash table to store the count of occurrences of each element in the input array.
- Traverse the input array again from index 0 to n-1, and increment the count of the corresponding element in the hash table.
- Traverse the input array again from index 0 to n-1, and for each element in the input array, check if the count of the corresponding element in the hash table is greater than 1. If it is, return the index of that element in the input array (i.e., i+1, since the function is expected to return a 1-based index). If no repeated element is found, the function returns -1.
Below is the Implementation of above approach
C++
#include <bits/stdc++.h>
using namespace std;
void firstRepeating(int arr[], int n) {
int max = -1;
for(int i = 0 ; i<n;i++){
if(max<arr[i]){
max = arr[i];
}
}
int hash[max+1]={0};
for(int i =0;i<n; i++){
hash[arr[i]]++;
}
int repeating=INT_MIN;
for(int i =0;i<n; i++){
if(hash[arr[i]]>1){
repeating=arr[i];
break;
}
}
if(repeating==INT_MIN){
cout << "There are no repeating elements";
}
else{
cout << "The first repeating element is : "
<<repeating;
}
}
int main()
{
int arr[] = { 10, 5, 3, 4, 3, 5, 6 };
int N = sizeof(arr) / sizeof(arr[0]);
firstRepeating(arr, N);
}
|
Java
import java.io.*;
class GFG {
static void firstRepeating(int[] arr, int n) {
int max = -1;
for (int i = 0; i < n; i++) {
if (max < arr[i]) {
max = arr[i];
}
}
int[] hash = new int[max + 1];
for (int i = 0; i < n; i++) {
hash[arr[i]]++;
}
int repeating = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
if (hash[arr[i]] > 1) {
repeating = arr[i];
break;
}
}
if (repeating == Integer.MIN_VALUE) {
System.out.println("There are no repeating elements");
} else {
System.out.println("The first repeating element is : " + repeating);
}
}
public static void main (String[] args) {
int[] arr = { 10, 5, 3, 4, 3, 5, 6 };
int N = arr.length;
firstRepeating(arr, N);
}
}
|
Python3
def firstRepeating(arr, n):
max_val = max(arr)
hash = [0] * (max_val+1)
for i in range(n):
hash[arr[i]] += 1
repeating = float('inf')
for i in range(n):
if hash[arr[i]] > 1:
repeating = arr[i]
break
if repeating == float('inf'):
print("There are no repeating elements")
else:
print("The first repeating element is:", repeating)
arr = [10, 5, 3, 4, 3, 5, 6]
N = len(arr)
firstRepeating(arr, N)
|
C#
using System;
public class Program
{
public static void FirstRepeating(int[] arr, int n)
{
int max = -1;
for (int i = 0; i < n; i++) {
if (max < arr[i]) {
max = arr[i];
}
}
int[] hash = new int[max + 1];
for (int i = 0; i < n; i++) {
hash[arr[i]]++;
}
int repeating = int.MinValue;
for (int i = 0; i < n; i++) {
if (hash[arr[i]] > 1) {
repeating = arr[i];
break;
}
}
if (repeating == int.MinValue) {
Console.WriteLine(
"There are no repeating elements");
}
else {
Console.WriteLine(
"The first repeating element is: "
+ repeating);
}
}
public static void Main()
{
int[] arr = { 10, 5, 3, 4, 3, 5, 6 };
int n = arr.Length;
FirstRepeating(arr, n);
}
}
|
Javascript
function firstRepeating(arr, n) {
let max_val = Math.max(...arr);
let hash = new Array(max_val + 1).fill(0);
for (let i = 0; i < n; i++) {
hash[arr[i]] += 1;
}
let repeating = Infinity;
for (let i = 0; i < n; i++) {
if (hash[arr[i]] > 1) {
repeating = arr[i];
break;
}
}
if (repeating == Infinity) {
console.log("There are no repeating elements");
} else {
console.log("The first repeating element is:", repeating);
}
}
let arr = [10, 5, 3, 4, 3, 5, 6];
let N = arr.length;
firstRepeating(arr,N);
|
Output
The first repeating element is : 5
Time Complexity: O(N).
Auxiliary Space: O(N).
The first for loop that finds the maximum element in the array has a time complexity of O(n). The second for loop that creates a hash array has a time complexity of O(n). The third for loop that checks for the first repeating element also has a time complexity of O(n). The array named ‘hash’ is created with max+1 elements so space O(max+1).
Since all three loops run sequentially, the total time complexity of the code is O(n).
Please Login to comment...