Find the largest subarray with sum of 0 in the given array

Problem

An array contains both positive and negative elements, find the largest subarray whose sum equals 0.

Example
int[] input = {4,  6,  3, -9, -5, 1, 3, 0, 2}
int output = {4,  6,  3, -9, -5, 1} of length 6

Solution

Method 1 - Brute force
This is simple. Will write later (incomplete)

Method 2 - Storing the sum upto ith element in temp array
Given an int[] input array, you can create an int[] tmp array where  

tmp[i] = tmp[i - 1] + input[i];

Each element of tmp will store the sum of the input up to that element.

Example

int[] input = {4 |  6| 3| -9| -5| 1| 3| 0| 2}
int[] tmp =   {4 | 10|13|  4| -1| 0| 3| 3| 5}

Now if you check tmp, you'll notice that there might be values that are equal to each other.For example, take the element 4 at index 0 and 3, element 3 at index 6 and 7. So, it means sum between these 2 indices has remained the same, i.e. all the elements between them add upto 0. So, based on that we get {6, 3, -9} and {0}.

Also, we know tmp[-1] = 0. When we have not started the array we have no element added to it. So, if we find a zero inside the tmp array, that means all the numbers starting 0th index to 5th index(where 0 exists in temp) are all 0s, so our subarray becomes {4,6,3, -9,-5,1}.

Out of {6, 3, -9}, {0} and {4,6,3, -9,-5,1}, last one is our answer as it is the largest sub array.

To sum it up
We notice that some values are same in tmp array. Let's say that this values are at indexes j an k with j < k, then the sum of the input till j is equal to the sum till k and this means that the sum of the portion of the array between j and k is 0! Specifically the 0 sum subarray will be from index j + 1 to k.

• NOTE: if j + 1 == k, then k is 0 and that's it! ;)
• NOTE: The algorithm should consider a virtual tmp[-1] = 0;
• NOTE: An empty array has sum 0 and it's minimal and this special case should be brought up as well in an interview. Then the interviewer will say that doesn't count but that's another problem! ;)

Here is the code

    public static string[] SubArraySumList(int[] array, int sum)
    {
        int tempsum;
        List<string> list = new List<string>();

        for (int i = 0; i < array.Length; i++)
        {
            tempsum = 0;

            for (int j = i; j < array.Length; j++)
            {
                tempsum += array[j];

                if (tempsum == sum)
                {
                    list.Add(String.Format("[{0}-{1}]", i, j));
                }
            }
        }
        return list.ToArray();
    }

Here is the solution using Hashmap, iterate over it again to get the max subarray:

public static void subArraySumsZero() {
    int [] seed = new int[] {1,2,3,4,-9,6,7,-8,1,9};
    int currSum = 0;
    HashMap<Integer, Integer> sumMap = new HashMap<Integer, Integer>();
    for(int i = 0 ; i < seed.length ; i ++){
        currSum += seed[i];
        if(currSum == 0){
            System.out.println("subset : { 0 - " + i + " }");
        }else if(sumMap.get(currSum) != null){
            System.out.println("subset : { " + (sumMap.get(currSum) + 1) + " - " + i + " }");
            sumMap.put(currSum, i);
        }else
            sumMap.put(currSum, i);
    }
    System.out.println("HASH MAP HAS: " + sumMap);
}

References

• http://stackoverflow.com/questions/5534063/zero-sum-subarray