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.

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

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 🙂
 

Get great deals at Amazon




Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Francisco
Guest
Francisco

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

int arr[2048] = {0};

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

Vishwajeet
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…

Jason
Guest
Jason

Nicely done (y)

Jana
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).

aparajit
Guest
aparajit

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

Coder
Guest
Coder

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

kishore
Guest
kishore

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

Ankit
Guest
Ankit

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

Noneof Yourbusiness
Guest
Noneof Yourbusiness

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

Noneof Yourbusiness
Guest
Noneof Yourbusiness

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.

Tony
Guest
Tony

He’s talking abt the second approach.

newbie
Guest
newbie

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

pratap
Guest
pratap

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

Is there anyway to collect the sparsely spread range?