Skip to content

Instantly share code, notes, and snippets.

@nashid
Last active October 30, 2016 13:59
Show Gist options
  • Save nashid/d21414e8a3c5011c56925fe6a777d069 to your computer and use it in GitHub Desktop.
Save nashid/d21414e8a3c5011c56925fe6a777d069 to your computer and use it in GitHub Desktop.
Longest Subarray with Zero Sum
public class ZeroSum {
/*
* @param input - integer array
* return - longest zero sum subarray list
*/
public int[] zeroSumLongest(int[] input) {
Map<Integer, Integer> lookUpMap = new HashMap<>();
int runningSum =0;
int[] zeroSumArray = new int[]{};
for(int i =0; i<input.length; i++) {
runningSum +=input[i];
int[] currentSumArray = new int[]{};
if(runningSum==0){
// if the sum up to this point becomes zero then this is the zero sum array
currentSumArray = Arrays.copyOfRange(input, 0, i+1);
}
else if(lookUpMap.containsKey(runningSum)) {
// if the sum is repeated that means we already have an enclosed subrray that can be summed up to zero
currentSumArray = Arrays.copyOfRange(input, lookUpMap.get(runningSum)+1, i+1);
}
// up date the maximum zero sum arrau
if(zeroSumArray.length < currentSumArray.length){
zeroSumArray = currentSumArray;
}
lookUpMap.put(runningSum, i);
}
return zeroSumArray;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment