Largest Sub-array With Sum Zero - Hashing Problem

Problem : Find the maximum length of the largest sub-array with sum zero.

Following is the implementation, where we store the sum at every index in hashmap and look for sum already being present in hashmap(only possible if sum of the sub-array is zero):

	package hashTables.problems;
	import java.util.HashMap;
	public class LargestSubWithSumZero {
	public static int maxLen(int arr[], int n) {
	HashMap<Integer, Integer> hM = new HashMap<Integer, Integer>();
	int sum = 0,maxLength = 0;
	for (int i = 0; i < n; i++) {
	sum += arr[i];
	if (arr[i] == 0 && maxLength == 0)
	maxLength = 1;
	if (sum == 0)
	maxLength = i + 1;
	Integer prevIndx = hM.get(sum);
	if (prevIndx != null)
	maxLength = Math.max(maxLength, i - prevIndx);
	else
	hM.put(sum, i);
	}
	return maxLength;
	}
	public static void main(String[] args) {
	int a6[]= {67,-3,3,-10,1,9,13,56};
	System.out.println(maxLen(a6, a6.length));
	}
	}

view raw LargestSubWithSumZero.java hosted with ❤ by GitHub