Find sub-array with 0 sum

Given an array of integers, check if array contains a sub-array having 0 sum. Also, prints end-points of all such sub-arrays.

 

For example,


Input:  { 4, 2, -3, -1, 0, 4 }

Sub-arrays with 0 sum are

{ -3, -1, 0, 4 }
{ 0 }
 

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

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 }

 


 

Naive solution would be to consider all sub-arrays and find its sum. If sub-array sum is equal to 0, we print it. The time complexity of naive solution is O(n3) as there are n2 sub-arrays and it takes O(n) time to find sum of its elements. The method can be optimized to run in O(n2) time by calculating sub-array sum in constant time.

 

C++

Download   Run Code


Java

Download   Run Code



Output:

Subarray [0..2]
Subarray [0..9]
Subarray [1..3]
Subarray [2..5]
Subarray [3..9]
Subarray [5..7]

 


 

We can easily solve this problem in linear time by using extra space. The idea is to use hashing.
 

Approach 1: (Using set)

 

We can 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.

C++

Download   Run Code


Java

Download   Run Code



Output:

Subarray exists

 

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


 

Approach 2: (Using multimap to print all subarrays)

 

We can use multimap to print all sub-arrays with 0 sum present in the given array. The idea is to create an empty multi-map to store ending index of all sub-arrays having given sum. We traverse the given array, and maintain sum of elements seen so far. If sum is seen before, there exists at-least one sub-array with 0 sum which ends at current index and we print all such sub-arrays.

C++

Download   Run Code


Java

Download   Run Code



Output:

Subarray [0..2]
Subarray [1..3]
Subarray [2..5]
Subarray [5..7]
Subarray [3..9]
Subarray [0..9]

 

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

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 🙂
 


    

  • Abhi shyam

    I think in the first example

    Input: { 4, 2, -3, -1, 0, 4 }

    Sub-arrays with 0 sum are

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

    this subset doesn’t satisfies the rule

    • Thanks Abhi for correcting us. The sub-array should be { -3, -1, 0, 4 }. We will update the post. Thanks again and happy coding 🙂

  • Sidd

    Could you give any tips or hints on how to print out all the possible subarrays using the HashSet method, instead of simply figuring out if there exists one subarray with sum equal to 0? Thanks.

    • Sidd, we have already covered that using multimap. Please read complete post. Thanks. Happy coding 🙂