Print all subarrays with 0 sum

Posted in

Vinay Khatri
Last updated on September 21, 2024

Problem Statement:

We need to find the subarrays with a sum having exactly 0. A subarray is a contiguous block of an array.

Sample Input:

`[1,2,3,-3,4]`

Sample Output:

`Starting and ending indices are 2 and 3 respectively`

Explanation: The subarray is [3,-3]

Brute force approach

An easy approach is to go through all of the subarrays one by one and see if the total of each one is equal to zero. This solution's complexity would be O(n2). Using Hashing is a superior option.

Efficient Approach

1. We can create a hash map that stores vectors of ending indices of sums of all the subarrays starting from 0 and ending at some index.
2. The keys of this hash map will be the sums of all subarrays starting from 0 and ending at some index.
3. If we find another subarray a [0]... a [j] which has a sum equal to some other subarray a [0]... a [i] whose sum is present in the hash map, then the elements between these ending indices will have 0 sum.
4. We then push the current subarray ending index into the respective vector and apply similar logic which solves this problem in an efficient manner as shown in the figure.

C++ Solution

```#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
vector<pair<int,int>> findSubarray(vector arr, int n ) {
ll sum=0;
vector<pair<int,int>>ans;
unordered_map<ll,vector>sum_map;
for(int i=0;i<n;i++){
sum+=arr[i];
if(sum==0){
ans.push_back({0,i});
}
if(sum_map.find(sum)!=sum_map.end()){
for(auto itr:sum_map[sum]){
ans.push_back({itr+1,i});
}
}
sum_map[sum].push_back(i);
}
return ans;
}
int main(){
vectorarr{1,2,-2,0,6};
vector<pair<int,int>>ans=findSubarray(arr,5);
cout<<"The starting and ending indices of subarrays with 0 sum are"<<"\n";
for(auto itr:ans){
cout<<itr.first<<" "<<itr.second<<"\n";
}
}```

Python

```def findSubArrays(arr,n):
hashMap = {}
res = []

sum1 = 0
for i in range(n):
# increment sum by element of array
sum1 += arr[i]

if sum1 == 0:
res.append((0, i))
list_pair = []

if sum1 in hashMap:
list_pair = hashMap.get(sum1)
for it in range(len(list_pair)):
res.append((list_pair[it] + 1, i))
list_pair.append(i)
hashMap[sum1] = list_pair
return res

def Output(output):
for i in output:
print ("Subarray found from index " +
str(i[0]) + " to " + str(i[1]))

if __name__ == '__main__':
arr = [1, -1, 2, -2]
n = len(arr)
res = findSubArrays(arr, n)

Output (res)
```

C#

```using System;
using System.Collections.Generic;

class Pair
{
public int first, second;
public Pair(int a, int b)
{
first = a;
second = b;
}
}

class Subarray
{
static List findSubArrays(int[] arr, int n)
{
Dictionary<int, List> map_sum = new Dictionary<int, List>();

// Maintains sum of elements from 0 to i
int sum = 0;

for (int i = 0; i < n; i++)
{
sum += arr[i];

if (sum == 0)
List list_pair = new List();

if (map_sum.ContainsKey(sum))
{
list_pair = map_sum[sum];
for (int it = 0; it < list_pair.Count; it++)
{
}
}
if(map_sum.ContainsKey(sum))
map_sum[sum] = list_pair;
else
}
}

{
for (int i = 0; i < answer.Count; i++)
{
Console.WriteLine("Subarray from Index " +
p.first + " to " + p.second);
}
}

public static void Main(String []args)
{
int[] arr = {1, -1, 2, -2};
int n = arr.Length;