Category Archives: Hash map

Finding the longest consecutive subset

Given an array of positive and negative numbers(distinct), How do we find the length of the longest consecutive subset?

For example consider the below array
{3, 6, 1, 2, 5, 7, 8}
It contains {5,6,7,8} as the longest consecutive subset. So the answer is 4.
Similarly for {2, 4, 6, 8}, the answer is 1 as there are no consecutive numbers.

Lets discuss two algorithms to solve this problem.

Method based on sorting: 
We sort all the elements in ascending order. This would take O(n log n) time. Then we compare the adjacent elements to check if they are consecutive. If any two elements are not consecutive, we break the sequence and update the maximum length. getMaxConsecutiveSubset1() method in the code implements this algorithm. The overall complexity of this algorithm is
O(n log n).
 
Method based on Hash map:

Let us take a Hash map which stores the all the elements with a flag for each which indicates if it is visited or not visited.
  • Initially we store all the elements to the map with visited flag as false. 
  • For each element do the following 
    • If it is not visited earlier 
      • Mark the element as visited 
      • Initiate a sequence of length 1 
      • Try to extend this sequence backward by marking the elements visited 
      • Try to extend this sequence forward by marking the elements visited 
      • Update the maximum sequence length

Here is the Java code which implements the above algorithm. It runs in O(n) time and O(n) space.

Finding the most occuring element ( mode) in an array

Given an array of numbers, how do we find the element which appears most number of times? In statistics this element is called mode.

A simple solution is to count the frequency of all the elements in the array and select the one with maximum frequency. The outer loop selects an element, and the inner loop counts the frequency of the element. Obviously this solution takes O(n2) time.
public static int mode( int[] array )
{
int maxCount = 1;
int maxElement = array[0];
for( int i = 0; i < array.length; i++ )
{
int count = 0;
for( int j = 0; j < array.length; j++ )
{
if( array[i] == array[j] )
count++;
}
if( maxCount < count )
{
maxCount = count;
maxElement = array[i];
}
}
return maxElement;
}

Second Method:
In this method we sort the array first. Then all the equal elements will be placed together. We can count the frequencies easily.

public static int mode( int[] array )
{
Arrays.sort(array); 
        //Assume first element as the mode
        int count = 1;
int maxCount = 1;
int maxElement = array[0]; 
        //start from the second element
        for( int i = 1; i < array.length; i++ )
{
            //array[i] is same as previous element; increment count
if( array[i-1] == array[i] )
{
count++;
}
else //new element; update the maxCount, maxElement and reset count
{
if( maxCount < count )
{
maxCount = count;
maxElement = array[i-1];
}
count = 1;
}
}
return maxElement;
}

This method takes O( n log n ) time because sorting is involved. It runs O(1) space because constant extra space is required.

Third Method:
This method is based on map. We first calculate the frequencies of all the elements in the array and store them in a map.
Then we iterate through the map to find the maximum occurring element. 

public static int mode( int[] array )
{
HashMap<Integer,Integer> map = new HashMap<Integer, Integer>();
int i; 
        //Calculate the frequency map 
        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 );
}
}
        //iterate through the map to find the maximum occurring element
Iterator iter = map.keySet().iterator();
int maxFreq = 0;
int maxElement = 0;
while( iter.hasNext() )
{
Integer key = (Integer)iter.next();
int value = map.get(key);
if( value > maxFreq )
{
maxFreq = value;
maxElement = key;
}
}
return maxElement;
}

This method runs in O(n) time but takes O(n) space for the map.

Finding the first repeated element in the array

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.


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?