Searching and Sorting: print all subarrays with 0 sum

Problem Statement:

You are given an array and you need to print all the sub array with the sum 0.

Example

Input: [ -3, -1, 0, 4 ]

Subarrays with zero-sum are

{ -3, -1, 0, 4 }
{ 0 }

Solution

The solution is very simple.

We will take the help of hashing.

We take a variable “sum” that will hold the sum of elements till now.

If the current sum is 0, then the sub array from index 0 till now is the index where the sum will be equal to 0.

Then if the current sum already exists in the hash table, then it will indicate that this sum was the sum of some sub-array from a[0] to a[i] and the same sum is obtained for the current sub array a[0] to arr[j].

Hence it means that the sum of sub-array a[i+1] to a[j] must be 0.

Example:

Consider the array [6, 3, -1, -3, 4, -2, 2]

Pass 1:

[6, 3, -1, -3, 4, -2, 2]
 ^

i = 0
sum = 6

Map  sum    index
     6   -> 0


Pass 2:

[6, 3, -1, -3, 4, -2, 2]
    ^

i = 1
sum = 9

Map  sum    index
     6   -> 0
     9   -> 1

Pass 3:

[6, 3, -1, -3, 4, -2, 2]
        ^

i = 2
sum = 8

Map  sum    index
     6   -> 0
     9   -> 1
     8   -> 2

Pass 4:

[6, 3, -1, -3, 4, -2, 2]
            ^

i = 3
sum = 5

Map  sum    index
     6   -> 0
     9   -> 1
     8   -> 2
     5   -> 3

Pass 5:

[6, 3, -1, -3, 4, -2, 2]
               ^

i = 4
sum = 9
vector {(2, 4)}

Map  sum    index
     6   -> 0
     9   -> 1, 4
     8   -> 2
     5   -> 3

Pass 6:

[6, 3, -1, -3, 4, -2, 2]
                   ^

i = 5
sum = 7
vector {(2, 4)}

Map  sum    index
     6   -> 0
     9   -> 1, 4
     8   -> 2
     5   -> 3
     7   -> 5

Pass 7:

[6, 3, -1, -3, 4, -2, 2]
                   ^

i = 6
sum = 9
vector {(2, 4), (2,6), (5, 6)}

Map  sum    index
     6   -> 0
     9   -> 1, 4, 6
     8   -> 2
     5   -> 3
     7   -> 5

Hence, the sum of the elements from index (2, 4), (2, 6) and (5, 6) are equal to 0.

Solution in C++

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <stack> 
#include <unordered_map> 

using namespace std;
  
vector< pair<int, int> > get_sub_arrays(int arr[], int n)
{
    unordered_map<int, vector<int> > map;
   
    vector <pair<int, int>> out;
   
    int sum = 0;
   
    for (int i = 0; i < n; i++)
    {
        sum += arr[i];
   
        if (sum == 0)
            out.push_back(make_pair(0, i));
   
        if (map.find(sum) != map.end())
        {
            vector<int> vc = map[sum];
            for (auto it = vc.begin(); it != vc.end(); it++)
                out.push_back(make_pair(*it + 1, i));
        }
   
        map[sum].push_back(i);
    }
    return out;
}
   

int main()
{
    int arr[] = {6, 3, -1, -3, 4, -2, 2};
    int n = sizeof(arr)/sizeof(arr[0]);
   
    vector<pair<int, int> > result = get_sub_arrays(arr, n);

    if (result.size() == 0)
    {
        cout << "No subarray exists";
    }
    else
    {
      for (auto it = result.begin(); it != result.end(); it++)
         cout<<"Subarray with sum 0 is from "<<it->first <<" to "<<it->second<<endl;
    }
   
    return 0;
}

Output:

Subarray with sum 0 is from 2 to 4
Subarray with sum 0 is from 2 to 6
Subarray with sum 0 is from 5 to 6