CC-17 : Find longest harmonic subsequence.

Description:

A harmonic subsequence is a sequence of numbers where the maximum difference is 1. Given an array of integers arr, find and return the length of the maximum length subsequence that can be formed out of elements of arr.

Test cases and expected outputs:

Input Parameters	Expected outputs
intArray = {4,3,3,2,4,1,2,3};	Longest harmonic subsequence of size 5 can be formed
intArray = {4,4,4,4};	Longest harmonic subsequence of size 0 can be formed
intArray = {9,9,9,1,2,2,7};	Longest harmonic subsequence of size 3 can be formed
intArray5 = {2,6,4,8};	Longest harmonic subsequence of size 0 can be formed

Pseudocode:

The java method should accept following input parameters: arr (integer array).

Initialize a variable hMap of type HashMap to hold integers from arr as keys, and the frequency of these integers as the values.

Iterate through arr using a for loop with idx as a loop variable with initial value 0 and increment idx till it reaches arr.length-1:

If hMap does not contain key arr[idx], then put key-value pair arr[idx] and 1 to hMap.

If hMap contains key arr[idx]with value freq, then put key-value pair arr[idx] and freq+1 to hMap.

Initialize variable currentSubSeq=0, this will be used to store the length of current temporary harmonic subsequence that we have found.

Initialize variable lngstSubSeq=0, this will be used to store the length of longest harmonic subsequence that we have found.

Iterate through keys of hMap, and store current key in variable currInt in each iteration:

If hMap contains key currInt+1:

Set currentSubSeq to sum of frequencies of currInt and currInt+1.

If currentSubSeq > lngstSubSeq:

Set lngstSubSeq= currentSubSeq.

After above loop completes, lngstSubSeq contains the length of longest harmonic subsequence of arr. Return lngstSubSeq.

Code:

public int hashMapHarmonicSubarray(int[] arr) throws Exception{
	HashMap<Integer,Integer> hMap=new HashMap<Integer, Integer>();
	for (int idx=0; idx < arr.length; idx++) {
		if (hMap.containsKey(arr[idx])){
			int freq=hMap.get(arr[idx]);
			hMap.put(arr[idx], ++freq);
		}else {
			hMap.put(arr[idx], 1);
		}			
	}
	Iterator itr=hMap.keySet().iterator();
	int currInt=0; int currSubSeq=0; int lngstSubSeq=0; 
	while (itr.hasNext()) {
		currInt=(int) 
				itr.next();
		if (hMap.containsKey(currInt+1)) {
			currSubSeq=hMap.get(currInt)+hMap.get(currInt+1);
			if (currSubSeq > lngstSubSeq) {
				lngstSubSeq=currSubSeq;
			}
		}		
	}
	return lngstSubSeq;		
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

import java.util.HashMap;
import java.util.Iterator;


public class HashMapHarmonicSubarray {
	
public int hashMapHarmonicSubarray(int[] arr) throws Exception{
	HashMap<Integer,Integer> hMap=new HashMap<Integer, Integer>();
	for (int idx=0; idx < arr.length; idx++) {
		if (hMap.containsKey(arr[idx])){
			int freq=hMap.get(arr[idx]);
			hMap.put(arr[idx], ++freq);
		}else {
			hMap.put(arr[idx], 1);
		}			
	}
	Iterator itr=hMap.keySet().iterator();
	int currInt=0; int currSubSeq=0; int lngstSubSeq=0; 
	while (itr.hasNext()) {
		currInt=(int) 
				itr.next();
		if (hMap.containsKey(currInt+1)) {
			currSubSeq=hMap.get(currInt)+hMap.get(currInt+1);
			if (currSubSeq > lngstSubSeq) {
				lngstSubSeq=currSubSeq;
			}
		}		
	}
	return lngstSubSeq;		
}
	
	
    
public static void main(String[] args) {
		
	HashMapHarmonicSubarray hp=new HashMapHarmonicSubarray();
	int retVal;
	try {
	int[] intArray1 = {4,3,3,2,4,1,2,3};
	printArraySummary(intArray1, "Original Array:");
	retVal=hp.hashMapHarmonicSubarray(intArray1);
	System.out.print("Longest subarray of size "+retVal+ " can be formed");
			
	int[] intArray2 = {4,4,4,4};
	printArraySummary(intArray2, "Original Array:");
	retVal=hp.hashMapHarmonicSubarray(intArray2);
	System.out.print("Longest subarray of size "+retVal+ " can be formed");
			
	int[] intArray3 = {9,9,9,1,2,2,7};
	printArraySummary(intArray3, "Original Array:");
	retVal=hp.hashMapHarmonicSubarray(intArray3);
	System.out.print("Longest subarray of size "+retVal+ " can be formed");
			
	int[] intArray4 = {1,2,3,4};
	printArraySummary(intArray4, "Original Array:");
	retVal=hp.hashMapHarmonicSubarray(intArray4);
	System.out.print("Longest subarray of size "+retVal+ " can be formed");
			
	int[] intArray5 = {2,6,4,8};
	printArraySummary(intArray5, "Original Array:");
	retVal=hp.hashMapHarmonicSubarray(intArray5);
	System.out.print("Longest subarray of size "+retVal+ " can be formed");
			
			
	}catch (Exception exception) {
	System.out.print("Exception: "+ exception);
	exception.printStackTrace();
	}
				
}

public static void printArraySummary(int[] intArray, String label) throws Exception {
   	// Case 1: The input Array is null !!
	if (intArray == null) { System.out.println("\n\n Input Array was null !! \n"); return; }
	// Case 2: Print input Array by index (first to last)
	System.out.println();
	System.out.println("************************************************************************");
	System.out.print(label+" : ");
	int arrayIndex=0;
	for (arrayIndex=0; arrayIndex< intArray.length; arrayIndex++) {
			System.out.print(intArray[arrayIndex]);
			if (arrayIndex< intArray.length-1) {System.out.print(",");}
	} 
	System.out.println();
	System.out.println("*************************************************************************");
	System.out.println();
	Thread.sleep(2000);
	return;
}

}