Find subarray with 0 sum

Subarray with 0 sum

Given an array of signed integers, find subarray with 0 sum. The first thing, you need to understand is : there is difference between subarray and subset of an array. In subarray all the elements are contiguous. So, in this question, find set of contiguous elements that is subarray with sum zero. For example, consider following arrays
A = [1,4,3,-1,2,-5,1], sum of sub array between index 2 and 6 [3,-1,2,-5,1] is zero. There may be more than one such subarrays in array.

Brute force method
Brute force solution will be to find all subarrays of given array and then add them individually to see if any of them adds up to zero. Subarrays will be of size 1 to size N and there will be N * (N -1)/2 sub arrays. Complexity of this method is O(n2).

def subarrayWithZeroSum(a):
	subarrayRanges = [];
	for i in range(len(a)):
		sum = 0;
		for j in range(i, len(a)):
			sum += a[j];
			if(sum == 0) :
				 subarray = (i,j);
				 subarrayRanges.append(subarray);
	return subarrayRanges
 
print subarrayWithZeroSum([4, 6, 3, -9, -5, 1, 3, 0, 2])

Subarray with zero sum : Using a hash
Basic idea is that, if sum for two different length subarrays starting at index 0 is zero, then the subarray with length equal to difference of these two subarrays adds up to zero. Let’s say that there are index i and k, such that sum from 0 to i is equal to sum of array elements from o to k, then all elements between i+1 to k add up to zero!

So, create a table/hash T[] of size N where T[i] represents sum of all elements till i index. Once done for all elements of array, check if there are i and j such that T[i] == T[j] and i != j. If yes, then we have a subarray of length j-i+1 length which adds up to zero. Simple concept and implementation is simpler.

Subarray with 0 sum implementation

#include<stdio.h>
#include<stdlib.h>
#include <math.h>
 
void subarrayWithZeroSum(int a[], int n){
  int i, j;
  int T[n];
  T[0] = a[0];
 
  for(i=1; i<n; i++){
    T[i] = T[i-1] + a[i];
    if(T[i] == 0){
        printf("\n Sub array from %d to %d adds up to zero" , 0, i);
    }
    for(j=0; j<i; j++){
       	if(T[i] == T[j]){
       		printf("\n Sub array from %d to %d adds up to zero", 
                            j+1,i);
       	}
    }
  }
}
int main(){
   int a[] = {4, 6, 3, -9, -5, 1, 3, 0, 2};
   int n = sizeof(a)/sizeof(a[0]);
   subarrayWithZeroSum(a,n);
   return 0;
}

Complexity of algorithm to find subarray with 0 sum is O(n2) with extra O(N) space but can be reduced to O(n) with use of hash, however, in that case our space complexity may be proportional to the maximum sum subarray.

Please share if there is something wrong or missing. Ig you are interested to contribute to algorithms and me, please contact us.

  • Andrew

    Why use additional memory space?

    A better solution that do not use additional memory:
    for(i=0;i<n;i++){
    int sum=0;
    for(j=i;j<n;j++)
    if(0==(sum+=a[j]))
    printf("n Sub array from %d to %d adds up to zero" , i,j);
    }

  • Andrei

    Why use additional memory space if it’s really not necessary?

    A simple and faster solution that do not use additional memory:
    for(i=0;i<n;i++){
    int sum=0;
    for(j=i;j<n;j++)
    if(0==(sum+=a[j]))
    printf("n Sub array from %d to %d adds up to zero" , i,j);
    }

    • http://algorithmsandme.com/ Jitendra Sangar

      Thanks for the comment. Just added this method. However, it has complexity of O(n2) compared to O(n) with O(n) space complexity in second method.