Check if subarray with 0 sum is exists or not

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

 

For example,


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++

Download   Run Code


Output:


Subarray exists

Java

Download   Run Code


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 ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 

Get great deals at Amazon




Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
H. Guijt
Guest
H. Guijt

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.

Roshan
Guest
Roshan

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

Roshan
Guest
Roshan

by mistake, ign0re

Sravan
Guest
Sravan

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?

NeelLohit
Guest
NeelLohit

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.

Cke
Guest

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

Am I right?

Cke
Guest

Yes I’m. Tested it ou your code!

Cke
Guest

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

Yusuf Belim
Guest
Yusuf Belim

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

Yusuf Belim
Guest
Yusuf Belim

Please ignore

sneh
Guest
sneh

{2, -3, 3}
the algorithm will return True but there is no subarray with zero sum.

sneh
Guest
sneh

apology, {-3, 3}