# 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(n^{2}).

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(n^{2}) 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.