Print all sub-array with 0 sum

Given an array of integers, print all subarrays having 0 sum.

 

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 }

 


 

Approach 1: Naive solution

 

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]

 


 

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]

 

 
 

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 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
Abhi shyam
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

Francisco
Francisco

Your second approach has a O(n^2) time complexity, consider:

int arr[2048] = {0};

Sam

I would like to point out a mistake.

The problem statement uses the term “sub-array”, but all of the solutions deal with only contiguous sub-arrays.

For example, the complete list of sub-arrays for [1,2,3] are as follows;

()
(1,)
(2,)
(3,)
(1, 2)
(1, 3)
(2, 3)
(1, 2, 3)

I think that in the problem statement the term “sub-array” should be replaced with “contiguous sub-array”. Or else the solutions should be updated to reflect the problem statement. If my understanding of the terminology or of set theory is wrong, please let me know.

Sorry for complaining. Thank you for providing us with techie delight, it’s an excellent resource.

wpDiscuz