Find the first repeated element in an array by its index

Objective: Given an array of integers, find out the first repeated element. First repeated element means the element occurs atleast twice and has smallest index.

Input: An Array

Output: The first repeated element

Examples :

Array {1,1,3,4,6,7,9} first repeated Number : 1
Array {7,2,2,3,7} first repeated Number : 7
Array {5,3,3,3,3,3,3,3,4,4,4,5,3} first repeated Number : 5

Approach:

Naive Solution :

Use two for loops. Time Complexity O(N2).

Better Solution: Using HastSet, Time Complexity O(N).

  • Take a variable say index = -1.
  • Initialize a HashSet.
  • Navigate the array from right to left(backwards) taking one element at a time
  • if HashSet doesnt contain element, add it
  • if HashSet contains then update the index with current index in navigation.
  • At the end index will be updated by the element which is repeated and has the lowest index.

Complete Code:

import java.util.HashSet;
public class FirstRepeatingelement {
public int find(int [] arrA){
int index = 1;
HashSet<Integer> hs = new HashSet<>();
for(int i = arrA.length1;i>=0;i){
if(hs.contains(arrA[i])){
index = i;
}else{
hs.add(arrA[i]);
}
}
return arrA[index];
}
public static void main(String args[]){
int [] a = {1,2,5,7,5,3,10,2};
FirstRepeatingelement f = new FirstRepeatingelement();
System.out.println("{1,2,5,7,5,3,10,2}");
System.out.println("first repeated element by index is : " + f.find(a));
}
}

Output:

{1,2,5,7,5,3,10,2}
first repeated element by index is : 2

2 thoughts on “Find the first repeated element in an array by its index”

  1. Code is wrong
    a)left parenthesis missing in System.out.println”{1,2,5,7,5,3,10,2}”);
    b) for loop needs to stop at i >=0 else it never enters as it is

    Reply

Leave a Reply to tutorialhorizon Cancel reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.