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

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 🙂

Subscribe
Notify of
Guest
Francisco

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

int arr[2048] = {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
Jason

Nicely done (y)

Guest
Jana

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
kishore

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

Guest
Ankit

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
Tony

He’s talking abt the second approach.

Guest
newbie

is it better to use your way
when to use lists and when to use maps
ps: the code is in kotlin

Guest
pratap

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

Is there anyway to collect the sparsely spread range?

Guest
TusharS

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?