# Print all sub-arrays with 0 sum

Given an array of integers, print all sub-arrays with 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 }

Related Post: Check if subarray with 0 sum is exists or not

##### 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.

## Java

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 multimap 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.

## Java

Output:

Subarray [0..2]
Subarray [1..3]
Subarray [2..5]
Subarray [5..7]
Subarray [3..9]
Subarray [0..9]     (8 votes, average: 4.88 out of 5) Loading...

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 🙂 Subscribe
Notify of Guest
Francisco

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

int arr = {0}; Guest

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. Guest
Vishwajeet

here they have given subarray problem…there is subsequence problem also
it can be solved with dynamic programming you can learn this concept onwards… Guest

Nicely done (y) Guest

this has to be contiguous subarrays for the size of the set of all subarrays of an array would be of O(2^n) instead of O(n^2). Guest
aparajit

hey plz send a code in c also… for the hashing one. Guest

what’s the time complexity of the second approach..? is O(N^2) the best solution possible..? Guest

It’s O(n) as unordered_map is hash based and takes O(1) time for its operations. Guest

Yes it is, as there can be O(N^2) subarrays satisfying the conditions (think of an array containing only 0s), so just printing the solution is O(n^2). Guest

Also, realizing that the best solution is O(n^2), one can build a sumLeftOfMe and sumRightOfMe array in linear time, and then check for all i <= j if sum – sumLeftOfMe – sumRightOfMe == 0. Guest

He’s talking abt the second approach. Guest

i used list instead
is it better to use your way
when to use lists and when to use maps
ps: the code is in kotlin Guest

For a given subset of following:
[-1, 0, 1, 2, -1, -4]

Is there anyway to collect the sparsely spread range? Guest

Tried in python3 Guest

but when you find sum, how do you know that you found sum with lowest “index” value ?
Since find uses binary search it could find any one of your sums so you can miss some of them?
Thanks in advance 🙂 Guest

std::unordered_multimap::find doesn’t use binary search algorithm. It uses a hash function to find a key in near-constant time. Guest

Both versions of your solution that use set and map (bool version and print all pairs version) seem to assume that the sub-array somehow starts from 0th index. Is it correct to say that?
The solutions don’t seem to work for a more generic case where you have a target sum given and the subarrays are in middle of the array.

For eg:
Array: { 1, -3, 4, 8, 1, 0, 9 } target: 9
Expected output should have the indices of these three sub-arrays (-3, 4, 8) (8, 1) and 9 Guest

I studied these sorts of questions and became a better programmer. That said, I wouldn’t want to work somewhere where they asked me to find a “zero sum sub array” in an interview