CC-6 : Find Subarrays with sum k.

Description:

Given integer array arr, and target sum k, find the count of subarrays of arr that sum up to k.

Test cases and expected outputs:

Input Parameters	Expected outputs
arr={2,3,2,4}; k=5;	Count of subarrays with sum 5 is 2
arr={2,3,2,2,4,1,3}; k=4;	Count of subarrays with sum 4 is 3

Pseudocode:

The java method should accept following input parameters: arr (integer array) and integer k (target sum).

Initialize a variable hMap of type HashMap to hold subarray sums and their counts.

Initialize variable subArrSum to 0, we will use this variable to track subarray that sum up to k.

Initialize variable subArrayCnt to 0, we will use this variable to track number of subarrays that sum up to k.

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:

Increment subArrSum by arr[idx].

If hMap does not contain key equal to subArrSum-k, then add 0 to subArrCnt.

If hMap contains key equal to subArrSum-k, then add value corresponding to key subArrSum-k to subArrCnt.

If hMap does not contain key equal to subArrSum, then add key subArrSum and add value 1 to hMap.

If hMap contains key equal to subArrSum, then add key subArrSum and add value equal to current value of key subArrSum, incremented by 1 to hMap.

After completion of above loop, subArrCnt contains the count of subArrays that sum up to k. return subArrSum.

Code:

public int hashMapSubarraysWithSumK(int[] arr, int k) throws Exception{
	HashMap<Integer,Integer> sumMap=new HashMap<Integer, Integer>();
	sumMap.put(0, 1); int subArrSum=0; int subArrCnt=0;	
	for (int idx=0; idx < arr.length; idx++) {
		subArrSum=subArrSum+arr[idx];
		subArrCnt=subArrCnt+sumMap.getOrDefault(subArrSum-k, 0);
		sumMap.put(subArrSum, sumMap.getOrDefault(subArrSum, 0)+1);
	}		
	return 	subArrCnt;
}

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;


public class HashMapSubarraysWithSumK {
	
public int hashMapSubarraysWithSumK(int[] arr, int k) throws Exception{
	HashMap<Integer,Integer> sumMap=new HashMap<Integer, Integer>();
	sumMap.put(0, 1); int subArrSum=0; int subArrCnt=0;	
	for (int idx=0; idx < arr.length; idx++) {
		subArrSum=subArrSum+arr[idx];
		subArrCnt=subArrCnt+sumMap.getOrDefault(subArrSum-k, 0);
		sumMap.put(subArrSum, sumMap.getOrDefault(subArrSum, 0)+1);
	}		
	return 	subArrCnt;
}
	
	
    
public static void main(String[] args) {
	
	HashMapSubarraysWithSumK hp=new HashMapSubarraysWithSumK();
	int retVal;
	try {
	int[] arr1={2,3,2,4};
	int k=5;
	printArraySummary(arr1, "The input array");
	retVal=hp.hashMapSubarraysWithSumK(arr1,k);
	System.out.println("Count of subarrays with sum "+k+" is "+retVal);
			
			
	int[] arr2={2,3,2,2,4,1,3};
	k=4;
	printArraySummary(arr2, "The input array");
	retVal=hp.hashMapSubarraysWithSumK(arr2,k);
	System.out.println("Count of subarrays with sum "+k+" is "+retVal);
			
	}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;
}

}