Print all subarrays with 0 sum

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>();

    	List answer = new 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)
            	answer.Add(new Pair(0, i));
        	List list_pair = new List();
       	 
        	if (map_sum.ContainsKey(sum))
        	{
            	list_pair = map_sum[sum];
            	for (int it = 0; it < list_pair.Count; it++)
            	{
                	answer.Add(new Pair(list_pair[it] + 1, i));
            	}
        	}
        	list_pair.Add(i);
        	if(map_sum.ContainsKey(sum))
            	    map_sum[sum] = list_pair;
        	else
            	    map_sum.Add(sum, list_pair);
    	}
    	return answer;
	}

	static void print(List answer)
	{
    	for (int i = 0; i < answer.Count; i++)
    	{
        	Pair p = answer[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;
   	 
    	List answer = findSubArrays(arr, n);
    	if (answer.Count == 0)
        	Console.WriteLine("No subarray exists");
    	else
        	print(answer);
	}
}

People are also reading:

• Check if a subarray with 0 sum exists or not
• Find a Pair with the Given Sum in an Array
• Data Structure Interview Questions
• Bellman-Ford Algorithm
• DSA Binary Search Tree
• DSA: Binary Heap Tree
• Fibonacci Series
• Types of Data Structure
• Python Data Structure
• DSA – Dynamic Programming