Print all subarrays with 0 sum

Given an array, print all subarrays in the array which has sum 0.

Examples:

Input:  arr = [6, 3, -1, -3, 4, -2, 2,
             4, 6, -12, -7]
Output:  
Subarray found from Index 2 to 4
Subarray found from Index 2 to 6          
Subarray found from Index 5 to 6
Subarray found from Index 6 to 9
Subarray found from Index 0 to 10

A simple solution is to consider all subarrays one by one and check if sum of every subarray is equal to 0 or not. The complexity of this solution would be O(n^2).

A better approach is to use Hashing.

Do following for each element in the array

Maintain sum of elements encountered so far in a variable (say sum).
If current sum is 0, we found a subarray starting from index 0 and ending at index current index
Check if current sum exists in the hash table or not.
If current sum exists in the hash table, that means we have subarray(s) present with 0 sum that ends at current index.
Insert current sum into the hash table

Below are implementation of above idea –

C++

// C++ program to print all subarrays 
// in the array which has sum 0 
#include <iostream> 
#include <unordered_map> 
#include <vector> 
using namespace std; 
   
// Function to print all subarrays in the array which 
// has sum 0 
vector< pair<int, int> > findSubArrays(int arr[], int n) 
{ 
    // create an empty map 
    unordered_map<int, vector<int> > map; 
   
    // create an empty vector of pairs to store 
    // subarray starting and ending index 
    vector <pair<int, int>> out; 
   
    // Maintains sum of elements so far 
    int sum = 0; 
   
    for (int i = 0; i < n; i++) 
    { 
        // add current element to sum 
        sum += arr[i]; 
   
        // if sum is 0, we found a subarray starting 
        // from index 0 and ending at index i 
        if (sum == 0) 
            out.push_back(make_pair(0, i)); 
   
        // If sum already exists in the map there exists 
        // at-least one subarray ending at index i with 
        // 0 sum 
        if (map.find(sum) != map.end()) 
        { 
            // map[sum] stores starting index of all subarrays 
            vector<int> vc = map[sum]; 
            for (auto it = vc.begin(); it != vc.end(); it++) 
                out.push_back(make_pair(*it + 1, i)); 
        } 
   
        // Important - no else 
        map[sum].push_back(i); 
    } 
   
    // return output vector 
    return out; 
} 
   
// Utility function to print all subarrays with sum 0 
void print(vector<pair<int, int>> out) 
{ 
    for (auto it = out.begin(); it != out.end(); it++) 
        cout << "Subarray found from Index " << 
            it->first << " to " << it->second << endl; 
} 
   
// Driver code 
int main() 
{ 
    int arr[] = {6, 3, -1, -3, 4, -2, 2, 4, 6, -12, -7}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
   
    vector<pair<int, int> > out = findSubArrays(arr, n); 
   
    // if we didn’t find any subarray with 0 sum, 
    // then subarray doesn’t exists 
    if (out.size() == 0) 
        cout << "No subarray exists"; 
    else
        print(out); 
   
    return 0; 
} 

Java

// Java program to print all subarrays 
// in the array which has sum 0 
import java.io.*; 
import java.util.*; 
  
// User defined pair class 
class Pair  
{ 
    int first, second; 
    Pair(int a, int b)  
    { 
        first = a; 
        second = b; 
    } 
} 
  
public class GFG 
{ 
    // Function to print all subarrays in the array which  
    // has sum 0 
    static ArrayList<Pair> findSubArrays(int[] arr, int n) 
    { 
            // create an empty map  
            HashMap<Integer,ArrayList<Integer>> map = new HashMap<>(); 
  
            // create an empty vector of pairs to store  
            // subarray starting and ending index  
            ArrayList<Pair> out = new ArrayList<>(); 
  
            // Maintains sum of elements so far 
            int sum = 0; 
  
            for (int i = 0; i < n; i++)  
            { 
                // add current element to sum  
                sum += arr[i]; 
  
                // if sum is 0, we found a subarray starting  
                // from index 0 and ending at index i  
                if (sum == 0) 
                    out.add(new Pair(0, i)); 
                ArrayList<Integer> al = new ArrayList<>(); 
                  
                // If sum already exists in the map there exists  
                // at-least one subarray ending at index i with  
                // 0 sum  
                if (map.containsKey(sum)) 
                { 
                    // map[sum] stores starting index of all subarrays 
                    al = map.get(sum); 
                    for (int it = 0; it < al.size(); it++) 
                    { 
                            out.add(new Pair(al.get(it) + 1, i));  
                    } 
                } 
                al.add(i); 
                map.put(sum, al); 
            } 
            return out; 
    }  
  
    // Utility function to print all subarrays with sum 0 
    static void print(ArrayList<Pair> out) 
    { 
            for (int i = 0; i < out.size(); i++) 
            { 
                Pair p = out.get(i); 
                System.out.println("Subarray found from Index "
                        + p.first + " to " + p.second);  
            } 
    } 
  
    // Driver code 
    public static void main(String args[]) 
    { 
            int[] arr = {6, 3, -1, -3, 4, -2, 2, 4, 6, -12, -7}; 
            int n = arr.length; 
              
            ArrayList<Pair> out = findSubArrays(arr, n); 
              
            // if we did not find any subarray with 0 sum,  
            // then subarray does not exists  
            if (out.size() == 0) 
                System.out.println("No subarray exists"); 
            else
                print(out); 
    } 
} 
  
// This code is contributed by rachana soma 

Output:

Subarray found from Index 2 to 4
Subarray found from Index 2 to 6
Subarray found from Index 5 to 6
Subarray found from Index 6 to 9
Subarray found from Index 0 to 10

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

C++

Java

tags:

leave a comment

0 Comments

Subscribe to Our Newsletter

Top Followed books