Print all subarrays with 0 sum

Posted in

Print all subarrays with 0 sum

Vinay Khatri
Last updated on September 10, 2022

    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:

    Tags:
    array

    Leave a Comment on this Post

    0 Comments