Print all subarrays with sum 0

Share

Problem: For a given array of positive or negative integers, find all sub-arrays whose sum is zero.

Problem Explanation: You are given an array a ={9, 2, -1, -3, 4,-2, 2, 4, 6, 0},  we can obtain four sub-arrays [-1, -3, 4 ], [2, -1, -3, 4, -2],           [-1 -3 4 -2 2] and [0]. Similarly, for array a = {6,3,-3,6} there is only one sub-array [3, -3].

Java Implementation

public void findSumZeroSubArrays(int[] arr) {
    Map<Integer, Integer> sumMap = new HashMap<Integer, Integer>();
    Integer sum = 0;
    for (int i = 0; i < arr.length; i++) {
        sum += arr[i];

        if (sum == 0) {
            printSubArray(arr, 0, i);
        }
        if (sumMap.get(sum) != null) {
            printSubArray(arr, sumMap.get(sum) + 1, i);
        } else {
            sumMap.put(sum, i);
        }
    }
}


public void printSubArray(int[] arr, int startIndex, int endIndex) {
    for (int i = startIndex; i <= endIndex; i++) {
        System.out.print(arr[i] + " ");
    }
    System.out.println();
}

TimeComplexity: O(n)

Note: If you find any other better way to approach to this problem or you find any issue/error in above code snippets/approaches – please share it in the comments section below and get a chance to enrol free of cost for an online Live Data Structure and Algorithm course (specially designed for interview preparation for software companies like Amazon, Google, Facebook, FlipKart, SnapDeal, HealthKart…)