vamsu
7/23/2018 - 1:02 PM

Print all sub arrays with zero sum

Print all sub arrays with zero sum

import java.util.*;
public class SubArraysWithZeroSum {
    public static void main(String args[]) {
        SubArraysWithZeroSum zeroSum = new SubArraysWithZeroSum();
        
        int[][] input = {
          null,
          {},
          {0},
          {1,0},
          {1,-1},
          {3,4,-7,3,1,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.printAll(input[i]);
        }
    }
    
    private void printAll(int[] input) {
        if(input == null || input.length == 0) {
            System.out.println("No zero sum sub arrays");
            return;
        }
        // <CurrentSum, Index>
        Map<Integer,List<Integer>> sumIndexTracker = new HashMap<Integer, List<Integer>>();
        // Adding 0 if the input starts with 0
        insert(sumIndexTracker, 0, -1);
        
        int currentSum = 0;
        for(int i=0; i< input.length; i++) {
            currentSum += input[i];
            if(sumIndexTracker.containsKey(currentSum)) {
                for(int index: sumIndexTracker.get(currentSum)) {
                    print(input, index+1, i);
                }
            } 
            insert(sumIndexTracker, currentSum, i);
        }
    }
    
    private void insert(Map<Integer,List<Integer>> sumTracker, int sum, int index) {
        if(!sumTracker.containsKey(sum)) {
            sumTracker.put(sum, new ArrayList<>());
        }
        sumTracker.get(sum).add(index);
    }
    
    private void print(int[] input, int start, int end) {
        System.out.print("[");
        for(int i=start; i<=end; i++) {
            System.out.print(input[i] + ",");
        }
        System.out.println("]");
    }
}