vamsu
7/23/2018 - 12:14 PM

Check if zero sum exists or not

Check if zero sum exists or not

import java.util.*;
public class CheckSubArrayZeroSumExists {
    public static void main(String args[]) {
        CheckSubArrayZeroSumExists zeroSum = new CheckSubArrayZeroSumExists();
        
        int[][] input = {
          null,
          {},
          {0},
          {1,0},
          {1,-1},
          {3,4,-7,3,1,-4,-2, -2}, 
          {1,2,3,-4}
        };
        for(int i=0; i< input.length; i++) {
            System.out.println("Input: " + Arrays.toString(input[i]) + 
                ", Result: " + zeroSum.exists(input[i]));   
        }
    }
    
    public boolean exists(int[] input) {
        if(input == null || input.length <= 0 ) {
            return false;
        }
        Set<Integer> sumTracker = new HashSet<>();
        sumTracker.add(0);
        
        int currentSum = 0;
        for(int current: input) {
            currentSum += current;
            //Trick: If we find a sum already seen before that implies zero sum exists.
            if(sumTracker.contains(currentSum)) {
                return true;
            }
            sumTracker.add(currentSum);
        }
        
        return false;
    }
}