Given an array which contains some duplicate entries, How do we find the element which appears first and is also repeated.
For example let us consider the array [10, 78, 45, 39, 22, 45, 78, 61].
The element 78 is repeated and it appears before all such repetitive elements. Note that, though two entries of 45 is found before 78, 78 is the required answer because it appears before 45 in the array.
The brute force approach which runs in O(n2) always works for this problem. This method is explained in my previous post.
In this post we will see the Hash map based algorithm. We iterate through the array once to find the frequencies of all the unique elements in the array.
We iterate through the array again to see the first element which appears more than once.
Here is the Java implementation.
For example let us consider the array [10, 78, 45, 39, 22, 45, 78, 61].
The element 78 is repeated and it appears before all such repetitive elements. Note that, though two entries of 45 is found before 78, 78 is the required answer because it appears before 45 in the array.
The brute force approach which runs in O(n2) always works for this problem. This method is explained in my previous post.
In this post we will see the Hash map based algorithm. We iterate through the array once to find the frequencies of all the unique elements in the array.
We iterate through the array again to see the first element which appears more than once.
Here is the Java implementation.
import java.util.HashMap;
/**
* Created with IntelliJ IDEA.
* User: Ravi
* Date: 9/20/13
* Time: 12:52 PM
* To change this template use File | Settings | File Templates.
*/
public class Main {
public static void main(String[] args)
{
int[] array = {1,2,3,3,2,4};
int firstRepInd = getFirstRepeatedIndex(array);
if( firstRepInd >= 0 )
{
System.out.println( array[firstRepInd] + " is the first repeated element");
}
else
{
System.out.println("No element is repeated!");
}
}
public static int getFirstRepeatedIndex(int[] array)
{
int resultInd = -1;
HashMap<Integer,Integer> map = new HashMap<Integer, Integer>();
int i;
for( i = 0; i < array.length; i++ )
{
//No entry in the map; add new with count 1
if( map.get(array[i]) == null )
{
map.put( array[i], 1 );
}
else //increment the count if already exists in the map
{
int valCount = map.get(array[i]);
map.put( array[i], ++valCount );
}
}
for( i = 0; i < array.length; ++i )
{
if( map.get(array[i]) > 1)
{
resultInd = i;
break;
}
}
return resultInd;
}
}
Similar Question: How do we find the first repeated character in the string?