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.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
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
Thanks bill. Corrected it.