**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(N^{2}).

**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:**

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

import java.util.HashSet; | |

public class FirstRepeatingelement { | |

public int find(int [] arrA){ | |

int index = –1; | |

HashSet<Integer> hs = new HashSet<>(); | |

for(int i = arrA.length–1;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