Given an array of integers, check if array contains a sub-array having 0 sum.

**Input:** { 3, 4, -7, 3, 1, 3, 1, -4, -2, -2 }

**Output:** Subarray with 0 sum exists

The sub-arrays with 0 sum are:

{ 3, 4, -7 }

{ 4, -7, 3 }

{ -7, 3, 1, 3 }

{ 3, 1, -4 }

{ 3, 1, 3, 1, -4, -2, -2 }

{ 3, 4, -7, 3, 1, 3, 1, -4, -2, -2 }

We can easily solve this problem in linear time by using hashing. The idea is to use set to check if sub-array with zero sum is present in the given array or not. We traverse the given array, and maintain sum of elements seen so far. If sum is seen before (i.e. sum exists in set), we return true as there exists at-least one sub-array with zero sum which ends at current index else we insert the sum into the set.

The time complexity of proposed solution is O(n) and auxiliary space used by the program is O(n).

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
#include <iostream> #include <unordered_set> using namespace std; // Function to check if sub-array with 0 sum is present // in the given array or not bool zeroSumSubarray(int A[], int n) { // create an empty set to store sum of elements of each // sub-array A[0..i] where 0 <= i < n unordered_set<int> set; // insert 0 into set to handle the case when sub-array with // 0 sum starts from index 0 set.insert(0); int sum = 0; // traverse the given array for (int i = 0; i < n; i++) { // sum of elements so far sum += A[i]; // if sum is seen before, we have found a sub-array with 0 sum if (set.find(sum) != set.end()) { return true; } else { // insert sum so far into set set.insert(sum); } } // we reach here when no sub-array with 0 sum exists return false; } // main function int main() { int A[] = { 4, 2, -3, -1, 0, 4 }; int n = sizeof(A)/sizeof(A[0]); zeroSumSubarray(A, n) ? cout << "Subarray exists": cout << "Subarray do not exist"; return 0; } |

`Output: `

Subarray exists

## Java

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
import java.util.Set; import java.util.HashSet; class ZeroSumSubarray { // Function to check if sub-array with 0 sum is present // in the given array or not public static Boolean zeroSumSubarray(int[] A) { // create an empty set to store sum of elements of each // sub-array A[0..i] where 0 <= i < arr.length Set<Integer> set = new HashSet<>(); // insert 0 into set to handle the case when sub-array with // 0 sum starts from index 0 set.add(0); int sum = 0; // traverse the given array for (int i = 0; i < A.length; i++) { // sum of elements so far sum += A[i]; // if sum is seen before, we have found a sub-array with 0 sum if (set.contains(sum)) { return true; } // insert sum so far into set set.add(sum); } // we reach here when no sub-array with 0 sum exists return false; } // main function public static void main (String[] args) { int[] A = { 4, -6, 3, -1, 4, 2, 7 }; if (zeroSumSubarray(A)) { System.out.println("Subarray exists"); } else { System.out.println("Subarray do not exist"); } } } |

`Output: `

Subarray exists

**Also See:** Print all sub-arrays with 0 sum

**Exercise:** Extend the solution for non-zero sum of sub-array.

**Thanks for reading.**

Please use our online compiler to post code in comments. To contribute, get in touch with us.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

Instead of arguments (int A[], int n), we can also use (std::initializer_list A). The function call would then be zeroSumSubArray ({4, 2, -3, -1, 0 4});, and the for-loop could use range-based for.

Hi, I would like to point out that your method above is predicated upon the condition that the linear addition of the elements in the array will at least once give a sum of zero. So for the array {5,1,-6,4,3} the algorithm works. But for the same elements in a different order e.g {5,1,4,-6,3}, this doesn’t work. That condition is not mentioned in the question. I think we should look for a more generalized solution to this problem and not just concentrate on the time complexity alone.

Thanks for sharing your concerns. The problem specifically targets a sub-array which are contiguous unlike a subsequence. Please check the difference here –

https://www.techiedelight.com/difference-between-subarray-subsequence-subset/

Let us know in case of any concerns.

Thank you so much for this clarification. I learnt a new thing today about something that I use on a daily basis. Just shows how much we don’t know 🙂

Instead of checking whether sum visited previously or not,can we check sum value in each iteration and see if sum is zero .If in any iteration sum is zero then there exists sub array whose sum is 0.No?

Thanks Sravan for sharing your thoughts. We can do it that way but the time complexity increases to

O(nwhich is not practical for this problem.^{2})Thanks for sharing your code. Please note that this will only print sub-arrays with zero sum starting from 0’th index.

Below fails.

int A[] = { 3,6,-6 };

Please ignore

code for the extended exercise we test with the sum so far minus the given sum

code in kotlin

[2, 3, 1, 4, -1, 6], the sum set will contain [0, 2, 5, 6, 10, 9, 15], no repeating.

please java code explain

This program is not working with the input

int[] A = { 4, -6, 3, -2, 4, 2, 7 };

and output is

Subarray do not existHello, There is in-fact no subarray. Sub-arrays are contiguous.

//Solution without set.

public class ZeroSumSubArray {

public static void main(String[] args) {

// TODO Auto-generated method stub

int[] A = { 4,-6,3,-2,2,4,7 };

int sum = 0;

for (int i = 0; i < A.length; i++) {

sum = sum + A[i];

System.out.println(sum);

if (sum == 0) {

System.out.println("ZeroSum Sub Array exit");

return;

}

}

System.out.println("ZeroSum Sub Array doesn't exit");

}

}

How is the time complexity O(n)? Set::find() has time complexity log(n). Therefore, time complexity here should be sum(log(i)) = log(n!) = nlogn?

Thanks for sharing your concerns.

You’re right about

std::settakingO(log(n))time but the solution uses hash-basedstd::unordered_setwhich retrieves elements inO(1)time.Confused.

The sum is being considered starting from the first element in the Java code.

How about this situation

{4, 5, 1, -6, 2}

The subarray {5,1,-6} sums to 0, but this would not be found by the Java code.

Am I missing something?

Thanks for sharing your concerns. Could you please run the solution, it’s working fine for your inputs –

https://techiedelight.com/compiler/?AEOjw5nDbPV4I8MVHC4b3W1INdvo

Ok. It works. My understanding was wrong 🙂

in JAVA example why you use the code fragment: “set.add(sum)” on line 32 ????

If anyone is having a hard time understanding how the algorithm works. You basically traverse through the array, and keep adding each element to the sum variable, and each time you store the new value of sum in a set.

Here come’s the tricky part.

[this is front part of the array] [sub array with zero sum] [this is back of the array]

now suppose the sum of the front part of the array was sum1, this would have been stored in our set. And you keep on iterating. When you have reached the end of the sub array with 0 sum, Guess what should be the value of the sum variable be? well it should be sum of the front part + sum of the sub array with sum 0. Which is sum of the front part. There sum would be sum1, which is already present in the set. And the function returns true.

Now what if the sub array with 0 sum is in the front.

[sub array with 0 sum] [back part of the array]

We already add 0 to our set before we start iterating. So after iterating over the sub array with contiguous sum the value of sum becomes 0, which is already present in the sub array, so boom shakalaka. You get a true value returned from the function.

This won’t work on say [3, -50, 1, -4]

Am I right?

Yes I’m. Tested it ou your code!

Ok, I see it now, you are working only on continious sub-arrays 😉

{2, -3, 3}

the algorithm will return True but there is no subarray with zero sum.

apology, {-3, 3}

this code fails for [4,2,3,1,0,4], it returns true though there are no zero sum sub arrays. Sum is repeating due to 0 in the array.

There is one zero sum subarray which is {0}.

int A[] = { 2, 1, -4, -1, 4 };

fails

by mistake, ign0re