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 🙂
 





Sort by:   newest | oldest | most voted
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)… Read more »
wpDiscuz