CC-19 : Find sum of intervals of duplicate integers in an array.

Description:

Given an array of integers, find the sum of intervals (sum of difference of indexes) of integers that repeat. Store the differences in an array and return the same.

Test cases and expected outputs:

Input Parameters	Expected outputs
intArray = {1,4,1,2,1,7,1};	Sum Intervals: : 12,0,8,0,8,0,12
intArray = {5,5,10,10,5,10};	Sum Intervals: : 5,4,4,3,7,5

Pseudocode:

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

Initialize a variable intFreqMap of type HashMap< Integer, ArrayList< Integer>> to hold Integers from input arrays as keys, and the indexes of these integers as the ArrayList.

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 intFreqMap does not contain key arr[idx], then put key-value pair arr[idx] and new ArrayList, to intFreqMap.

If intFreqMap contains key arr[idx]with value freq, then put key-value pair arr[idx] and put idx to value ArrayList, to intFreqMap.

Initialize an integer array named sumIntervals with same size as arr.

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:

For each integer, extract the arrays list of its integer from intFreqMap and store it in Arraylist variable idxs.

Iterate through idxs and calculate sum of difference indexes of current integer and all its duplicates. Store the sum in array sumIntervals.

After above loop completes, sumIntervals contains sum of intervals of repeated integer in arr. Return sumIntervals.

Code:

public int[] hashMapSumItervals(int[] arr) throws Exception{
	HashMap< Integer,ArrayList< Integer>> intFreqMap=new HashMap< Integer, ArrayList< Integer>>();
	for (int idx=0; idx < arr.length; idx++) {
		intFreqMap.putIfAbsent(arr[idx], new ArrayList<Integer>());			
		intFreqMap.get(arr[idx]).add(idx);
	}		
	int[] sumIntervals=new int[arr.length];
	for (int idx=0; idx < arr.length; idx++) {
		int i=arr[idx];
		ArrayList idxs=intFreqMap.get(i);
		Iterator< Integer> itr=idxs.iterator();
		int i_idx=0; int sumLeft=0; int sumRight=0;
		int leftIdxCnt=0; int rightIdxCnt=0;
		while (itr.hasNext()) {
			i_idx=itr.next();
			if (i_idx < idx) {
				sumLeft+=i_idx;
				leftIdxCnt++;
			}
			if (i_idx > idx) {
				sumRight+=i_idx;
				rightIdxCnt++;
			}
		}
		sumLeft=(leftIdxCnt*idx)-(sumLeft);
		sumRight=sumRight-(rightIdxCnt*idx);
		sumIntervals[idx]=sumLeft+sumRight;		
	}
	return sumIntervals;
}

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.ArrayList;
import java.util.HashMap;
import java.util.Iterator;


public class HashMapSumIntervals {
	
public int[] hashMapSumItervals(int[] arr) throws Exception{
	HashMap< Integer,ArrayList< Integer>> intFreqMap=new HashMap< Integer, ArrayList< Integer>>();
	for (int idx=0; idx < arr.length; idx++) {
		intFreqMap.putIfAbsent(arr[idx], new ArrayList<Integer>());			
		intFreqMap.get(arr[idx]).add(idx);
	}		
	int[] sumIntervals=new int[arr.length];
	for (int idx=0; idx < arr.length; idx++) {
		int i=arr[idx];
		ArrayList idxs=intFreqMap.get(i);
		Iterator< Integer> itr=idxs.iterator();
		int i_idx=0; int sumLeft=0; int sumRight=0;
		int leftIdxCnt=0; int rightIdxCnt=0;
		while (itr.hasNext()) {
			i_idx=itr.next();
			if (i_idx < idx) {
				sumLeft+=i_idx;
				leftIdxCnt++;
			}
			if (i_idx > idx) {
				sumRight+=i_idx;
				rightIdxCnt++;
			}
		}
		sumLeft=(leftIdxCnt*idx)-(sumLeft);
		sumRight=sumRight-(rightIdxCnt*idx);
		sumIntervals[idx]=sumLeft+sumRight;		
	}
	return sumIntervals;
}
		

    
public static void main(String[] args) {
	
	HashMapSumIntervals hp=new HashMapSumIntervals();
	int[] retVal;
	try {
	int[] intArray1 = {1,4,1,2,1,7,1};
	printArraySummary(intArray1, "Original Array:");
	retVal=hp.hashMapSumItervals(intArray1);
	printArraySummary(retVal, "Sum Intervals:");
			
	int[] intArray2 = {5,5,10,10,5,10};
	printArraySummary(intArray2, "Original Array:");
	retVal=hp.hashMapSumItervals(intArray2);
	printArraySummary(retVal, "Sum Intervals:");
			
	}catch (Exception exception) {
	System.out.print("Exception: "+ exception);
	}
				
	}

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;
}

}