Subarrays with sum zero

Given an array of positive and negative integers, find number of subarrays with sum zero in that array. For example, in the array given below, there are two subarrays whose elements sum to zero.

Input:
A = [1,3,2,-1,5,4,-8,4,3,-7]
Output:
4
Explanation:
Sybarrays [-1,5,4,-8], [4,-8,4], [-1,5,4,-8,4,3,-7] and [4,3,-7] are subarrays with zero sum.

Brute force method solve this problem will be to find all subarrays of the given array and then add them individually to see if any subarray adds up to zero. There can be n * (n-1) subarrays for a given array of size n, so the complexity of brute force solution is O(n2).

package com.company;

import java.util.Arrays;
import java.util.HashMap;

/**
 * Created by sangar on 3.12.18.
 */
public class SubarrayWithZeroSum {
    public int [] findSubarrayWithZeroSumBrute(int[] a){
        int len = a.length;
        int count = 0;
        for(int i=0; i<len; i++){
            int  sum  = 0;
            for(int j=i; j<len; j++){
                sum += a[j];
                if(sum == 0){
                    count++;
                }
            }
        }
        return count;
    }
}

Thought proces

A subarray is a contiguous part of an array. Let’s say we find the sum of subarray starting at 0 and ending at any index i. So, T[i] represents the sum of subarray A[0..i].

What if we have two indices i and j; such that i< j and T[i] = T[j]. In this case, all the elements which are from index i+1 and index j add up to zero and that is our subarray with sum zero. Length of subarray with sum zero will be j-i+1.

Show me implementation

package com.company;

import java.util.Arrays;
import java.util.HashMap;

/**
 * Created by sangar on 3.12.18.
 */
public class SubarrayWithZeroSum {
    public int [] findSubarrayWithZeroSum(int[] a){

        int len = a.length;
        int [] T = new int[len];

        T[0] = a[0];
        for(int i=1; i<len; i++){
            T[i] = T[i-1] + a[i];
        }

        //Complexity of below code is O(n^2)
        int count = 0;
        for(int i=0; i<len; i++){
            for(int j=i+1; j<len; j++){
                if(T[i]== T[j]){
                    count++;
                }
            }
        }
        return count;
    }
}

The complexity of the implementation is O(n2) with an additional space complexity of O(n) to store sum till index i.

We can optimize it further by creating a hash of all the sums which we see while adding. When we add the index i to already calculated sum till index i-1, we check if the new sum is zero? If yes, then subarray from 0 to index i add up to zero. If there is already a sum present which is equal to the current sum then there is subarray with sum zero between index when we saw the sum last and current index.

Implementation with hashmap

package com.company;

import java.util.Arrays;
import java.util.HashMap;

/**
 * Created by sangar on 3.12.18.
 */
public class SubarrayWithZeroSum {

    public int [] findSubarrayWithZeroSumOptimized(int[] a){

        int len = a.length;
        HashMap<Integer, Integer> T = new HashMap<Integer, Integer>();
        T.put(0, 1);

        int sum  = 0 ;
        int count = 0;
        for(int i=0; i<len; i++){
            sum  += a[i];
            if(T.containsKey(sum)){
                count += T.get(sum);
                T.put(sum, count);
            }else{
                T.put(sum, 1);
            }
        }
        return count;
    }
}

The complexity of this method is O(n) with additional space of O(n) in worst case.

If you want to solve an advance version of the problem, read it here: subarrays with sum k.

Please share if there is something wrong or missing. If you are preparing for an interview, please signup for free interview kit.