Last active
October 30, 2016 13:59
-
-
Save nashid/d21414e8a3c5011c56925fe6a777d069 to your computer and use it in GitHub Desktop.
Longest Subarray with Zero Sum
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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