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
Related posts: Find if there is a subarray with 0 sum
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). sandharbnkamble
Below is the implementation of the above approach:
C++
// C++ program to print all subarrays// in the array which has sum 0#include <bits/stdc++.h>using namespace std;vector<pair<int, int> > findSubArrays(int arr[], int n){ // Array to store all the start and end // indices of subarrays with 0 sum vector<pair<int, int> > output; for (int i = 0; i < n; i++) { int prefix = 0; for (int j = i; j < n; j++) { prefix += arr[j]; if (prefix == 0) output.push_back({ i, j }); } } return output;}// Function to print all subarrays with 0 sumvoid print(vector<pair<int, int> > output){ for (auto it = output.begin(); it != output.end(); it++) cout << "Subarray found from Index " << it->first << " to " << it->second << endl;}// Driver codeint main(){ // Given array int arr[] = { 6, 3, -1, -3, 4, -2, 2, 4, 6, -12, -7 }; int n = sizeof(arr) / sizeof(arr[0]); // Function Call vector<pair<int, int> > output = findSubArrays(arr, n); // if we didn’t find any subarray with 0 sum, // then subarray doesn’t exists if (output.size() == 0) { cout << "No subarray exists"; } else { print(output); } return 0;}// This article is contributed by Arpit Jain |
Java
// Java program to print all subarrays// in the array which has sum 0import java.io.*;import java.util.*;// User defined pair classclass Pair{ int first, second; Pair(int a, int b) { first = a; second = b; }}public class GFG{ static ArrayList<Pair> findSubArrays(int[] arr, int n) { // Array to store all the start and end // indices of subarrays with 0 sum ArrayList<Pair> out = new ArrayList<>(); for (int i = 0; i < n; i++) { int prefix = 0; for(int j = i; j < n; j++){ prefix += arr[j]; if(prefix == 0) out.add(new Pair(i, j)); } } return out; } // Function to print all subarrays with 0 sum 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[]) { // Given array int[] arr = {6, 3, -1, -3, 4, -2, 2, 4, 6, -12, -7}; int n = arr.length; // Function Call ArrayList<Pair> out = findSubArrays(arr, n); // if we didn’t find any subarray with 0 sum, // then subarray doesn’t exists if (out.size() == 0) System.out.println("No subarray exists"); else print(out); }}// This code is contributed by sandharbnkamble. |
Python3
# User defined pair classclass Pair : first = 0 second = 0 def __init__(self, a, b) : self.first = a self.second = bclass GFG : @staticmethod def findSubArrays( arr, n) : # Array to store all the start and end # indices of subarrays with 0 sum out = [] i = 0 while (i < n) : prefix = 0 j = i while (j < n) : prefix += arr[j] if (prefix == 0) : out.append(Pair(i, j)) j += 1 i += 1 return out # Function to print all subarrays with 0 sum @staticmethod def print( out) : i = 0 while (i < len(out)) : p = out[i] print("Subarray found from Index " + str(p.first) + " to " + str(p.second)) i += 1 # Driver code @staticmethod def main( args) : # Given array arr = [6, 3, -1, -3, 4, -2, 2, 4, 6, -12, -7] n = len(arr) # Function Call out = GFG.findSubArrays(arr, n) # if we didn't find any subarray with 0 sum, # then subarray doesn't exists if (len(out) == 0) : print("No subarray exists") else : GFG.print(out) if __name__=="__main__": GFG.main([]) # This code is contributed by aadityaburujwale. |
C#
using System;using System.Collections.Generic;class GFG{ // Array to store all the start and end // indices of subarrays with 0 sum static List<Tuple<int, int>> findSubArrays(int[] arr, int n) { var output = new List<Tuple<int, int>>(); for (int i = 0; i < n; i++) { int prefix = 0; for (int j = i; j < n; j++) { prefix += arr[j]; if (prefix == 0) output.Add(Tuple.Create(i, j)); } } return output; } // Function to print all subarrays with 0 sum static void print(List<Tuple<int, int>> output) { foreach (var subArray in output) Console.Write("Subarray found from Index " + subArray.Item1 + " to " + subArray.Item2+"\n"); } // Driver code public static void Main() { // Given array int[] arr = { 6, 3, -1, -3, 4, -2, 2, 4, 6, -12, -7 }; int n = arr.Length; // Function Call List<Tuple<int, int>> output = findSubArrays(arr, n); // if we didn’t find any subarray with 0 sum, // then subarray doesn’t exists if (output.Count == 0) { Console.WriteLine("No subarray exists"); } else { print(output); } }}// This code is contributed by ratiagarwal. |
Javascript
// Javascript program to print all subarrays// in the array which has sum 0function findSubArrays(arr, n){ // Array to store all the start and end // indices of subarrays with 0 sum let out =[]; for (let i = 0; i < n; i++) { let prefix = 0; for (let j = i; j < n; j++) { prefix += arr[j]; if (prefix == 0) out.push([i, j]); } } return out;}// Function to print all subarrays with 0 sumfunction print(out){ for (let it of out) console.log("Subarray found from Index " + it[0] + " to " + it[1]);}// Driver code// Given arraylet arr = [ 6, 3, -1, -3, 4, -2, 2, 4, 6, -12, -7 ];let n = arr.length ;// Function Calllet out = findSubArrays(arr, n);// if we didn’t find any subarray with 0 sum,// then subarray doesn’t existsif (out.length == 0) { console.log("No subarray exists");}else { print(out);} // This code is contributed by poojaagarwal2. |
Output
Subarray found from Index 0 to 10 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
Time Complexity: O(N^2) since we are using 2 loops.
Auxiliary Space: O(1), as constant extra space is required.
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 already exists in the hash table then it indicates that this sum was the sum of some sub-array elements arr[0]…arr[i] and now the same sum is obtained for the current sub-array arr[0]…arr[j] which means that the sum of the sub-array arr[i+1]…arr[j] must be 0.
- Insert current sum into the hash table
Below is a dry run of the above approach:
Below is the implementation of the above approach:
C++
// C++ program to print all subarrays// in the array which has sum 0#include <bits/stdc++.h>using namespace std; // Function to print all subarrays in the array which// has sum 0vector< 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 0void 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 codeint 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 0import java.io.*;import java.util.*;// User defined pair classclass 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 |
Python3
# Python3 program to print all subarrays# in the array which has sum 0# Function to get all subarrays# in the array which has sum 0def findSubArrays(arr,n): # create a python dict hashMap = {} # create a python list # equivalent to ArrayList out = [] # tracker for sum of elements sum1 = 0 for i in range(n): # increment sum by element of array sum1 += arr[i] # if sum is 0, we found a subarray starting # from index 0 and ending at index i if sum1 == 0: out.append((0, i)) al = [] # If sum already exists in the map # there exists at-least one subarray # ending at index i with 0 sum if sum1 in hashMap: # map[sum] stores starting index # of all subarrays al = hashMap.get(sum1) for it in range(len(al)): out.append((al[it] + 1, i)) al.append(i) hashMap[sum1] = al return out# Utility function to print# all subarrays with sum 0 def printOutput(output): for i in output: print ("Subarray found from Index " + str(i[0]) + " to " + str(i[1]))# Driver Codeif __name__ == '__main__': arr = [6, 3, -1, -3, 4, -2, 2, 4, 6, -12, -7] n = len(arr) out = findSubArrays(arr, n) # if we did not find any subarray with 0 sum, # then subarray does not exists if (len(out) == 0): print ("No subarray exists") else: printOutput (out) # This code is contributed by Vikas Chitturi |
C#
// C# program to print all subarrays// in the array which has sum 0using System;using System.Collections.Generic;// User defined pair classclass Pair { public int first, second; public Pair(int a, int b) { first = a; second = b; }}class GFG{ // Function to print all subarrays // in the array which has sum 0 static List<Pair> findSubArrays(int[] arr, int n) { // create an empty map Dictionary<int, List<int>> map = new Dictionary<int, List<int>>(); // create an empty vector of pairs to store // subarray starting and ending index List<Pair> outt = new List<Pair>(); // 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) outt.Add(new Pair(0, i)); List<int> al = new List<int>(); // 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[sum]; for (int it = 0; it < al.Count; it++) { outt.Add(new Pair(al[it] + 1, i)); } } al.Add(i); if(map.ContainsKey(sum)) map[sum] = al; else map.Add(sum, al); } return outt; } // Utility function to print all subarrays with sum 0 static void print(List<Pair> outt) { for (int i = 0; i < outt.Count; i++) { Pair p = outt[i]; Console.WriteLine("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; List<Pair> outt = findSubArrays(arr, n); // if we did not find any subarray with 0 sum, // then subarray does not exists if (outt.Count == 0) Console.WriteLine("No subarray exists"); else print(outt); }}// This code is contributed by Rajput-Ji |
Javascript
// JavaScript program to print all subarrays// in the array which has sum 0// Function to print all subarrays in the array which// has sum 0function findSubArrays(arr, n){ // create an empty map let map = {}; // create an empty vector of pairs to store // subarray starting and ending index let out = []; // Maintains sum of elements so far let sum = 0; for (var 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([0, i]); // If sum already exists in the map there exists // at-least one subarray ending at index i with // 0 sum if (map.hasOwnProperty(sum)) { // map[sum] stores starting index of all subarrays let vc = map[sum]; for (let it of vc) out.push([it + 1, i]); } else map[sum] = []; // Important - no else map[sum].push(i); } // return output vector return out;} // Utility function to print all subarrays with sum 0function print(out){ for (let it of out) console.log("Subarray found from Index " + it[0] + " to " + it[1]);} // Driver codelet arr = [6, 3, -1, -3, 4, -2, 2, 4, 6, -12, -7];let n = arr.length; let out = findSubArrays(arr, n); // if we didn’t find any subarray with 0 sum,// then subarray doesn’t existsif (out.length == 0) console.log("No subarray exists");else print(out);// This code is contributed by phasing17. |
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
Time Complexity: O(N)
Auxiliary Space: O(N)
Approach 3: Finding subarrays with sum 0 using dynamic programming:
Algorithm:
1. Create an empty vector of pairs to store the starting and ending indices of all subarrays with a 0 sum.
2. Create an unordered map with the starting index of all subarrays that have the same sum.
3. Initialize variable “sum =0″.
4. Add a dummy index -1 to represent the empty subarray , i.e. ” sums[0].push_back(-1);”
5. Traverse the array from left to right:
- Add current element to the sum.
- If sum is already present in map, retrieve the vector of indices and add all subarrays beginning with those indices and ending with the current index to the output vector.
- In the map, add the current index to the vector of indices for the current total.
6. Return the output vector “out”.
Here’s the implementation of above algorithm:
C++
#include <bits/stdc++.h>using namespace std;vector<pair<int, int>> findSubArrays(int arr[], int n) { vector<pair<int, int>> out; unordered_map<int, vector<int>> sums; // map to store the starting index of all subarrays with the same sum int sum = 0; sums[0].push_back(-1); // add a dummy index -1 to represent the empty subarray for (int i = 0; i < n; i++) { sum += arr[i]; if (sums.find(sum) != sums.end()) { vector<int> indices = sums[sum]; for (int j = 0; j < indices.size(); j++) { out.push_back(make_pair(indices[j] + 1, i)); } } sums[sum].push_back(i); } return out;}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; }}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 (out.size() == 0) { cout << "No subarray exists"; } else { print(out); } return 0;}// This article is contributed by Vaibhav Saroj |
Java
import java.util.*;public class Main { // Function to find subarrays with the same sum public static List<Map.Entry<Integer, Integer>> findSubArrays(int[] arr, int n) { List<Map.Entry<Integer, Integer>> out = new ArrayList<>(); // Map to store the starting index of all subarrays with the same sum Map<Integer, List<Integer>> sums = new HashMap<>(); int sum = 0; // Add a dummy index -1 to represent the empty subarray sums.put(0, new ArrayList<>(Collections.singletonList(-1))); for (int i = 0; i < n; i++) { sum += arr[i]; if (sums.containsKey(sum)) { List<Integer> indices = sums.get(sum); for (Integer j : indices) { // Add found subarray range to the output list out.add(new AbstractMap.SimpleEntry<>(j + 1, i)); } } // Add current index to the sum's list of indices sums.computeIfAbsent(sum, k -> new ArrayList<>()).add(i); } return out; } // Function to print subarray ranges public static void print(List<Map.Entry<Integer, Integer>> out) { for (Map.Entry<Integer, Integer> entry : out) { System.out.println("Subarray found from Index " + entry.getKey() + " to " + entry.getValue()); } } public static void main(String[] args) { int[] arr = {6, 3, -1, -3, 4, -2, 2, 4, 6, -12, -7}; int n = arr.length; // Find subarrays with the same sum List<Map.Entry<Integer, Integer>> out = findSubArrays(arr, n); if (out.size() == 0) { System.out.println("No subarray exists"); } else { print(out); // Print the found subarray ranges } }}// This code is contributed by shivamgupta0987654321 |
Python3
def find_subarrays(arr): out = [] # Dictionary to store the starting index of all subarrays with the same sum sums = {0: [-1]} current_sum = 0 # Loop through the array for i, num in enumerate(arr): current_sum += num if current_sum in sums: indices = sums[current_sum] for j in indices: # Add found subarray range to the output list out.append((j + 1, i)) # Add the current index to the sum's list of indices if current_sum in sums: sums[current_sum].append(i) else: sums[current_sum] = [i] return outdef print_subarrays(subarrays): for start, end in subarrays: print(f"Subarray found from Index {start} to {end}")def main(): arr = [6, 3, -1, -3, 4, -2, 2, 4, 6, -12, -7] # Find subarrays with the same sum subarrays = find_subarrays(arr) if not subarrays: print("No subarray exists") else: print_subarrays(subarrays) # Print the found subarray rangesif __name__ == "__main__": main() # This code is contributed by akshitaguprzj3 |
C#
using System;using System.Collections.Generic;public class GFG{ // Function to find all subarrays with the same sum and store their starting and ending indices public static List<Tuple<int, int>> FindSubArrays(int[] arr) { List<Tuple<int, int>> outList = new List<Tuple<int, int>>(); Dictionary<int, List<int>> sums = new Dictionary<int, List<int>>(); int sum = 0; sums[0] = new List<int> { -1 }; // add a dummy index -1 to represent the empty subarray for (int i = 0; i < arr.Length; i++) { sum += arr[i]; if (sums.ContainsKey(sum)) { List<int> indices = sums[sum]; foreach (int j in indices) { outList.Add(new Tuple<int, int>(j + 1, i)); } } if (!sums.ContainsKey(sum)) sums[sum] = new List<int>(); sums[sum].Add(i); } return outList; } // Function to print the subarrays with the same sum public static void Print(List<Tuple<int, int>> outList) { foreach (Tuple<int, int> pair in outList) { Console.WriteLine("Subarray found from Index " + pair.Item1 + " to " + pair.Item2); } } public static void Main() { int[] arr = { 6, 3, -1, -3, 4, -2, 2, 4, 6, -12, -7 }; List<Tuple<int, int>> outList = FindSubArrays(arr); if (outList.Count == 0) { Console.WriteLine("No subarray exists"); } else { Print(outList); } }} |
Javascript
// Function to find subarrays with the same sumfunction findSubArrays(arr) { const out = []; const sums = new Map(); // Map to store the starting index of all subarrays with the same sum let sum = 0; sums.set(0, [-1]); // Add a dummy index -1 to represent the empty subarray for (let i = 0; i < arr.length; i++) { sum += arr[i]; if (sums.has(sum)) { const indices = sums.get(sum); for (const index of indices) { out.push([index + 1, i]); } } if (!sums.has(sum)) { sums.set(sum, [i]); } else { sums.get(sum).push(i); } } return out;}// Function to print the subarraysfunction print(out) { for (const subarray of out) { console.log(`Subarray found from Index ${subarray[0]} to ${subarray[1]}`); }}// Main functionfunction main() { const arr = [6, 3, -1, -3, 4, -2, 2, 4, 6, -12, -7]; const out = findSubArrays(arr); if (out.length === 0) { console.log("No subarray exists"); } else { print(out); }}// Calling the main functionmain(); |
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
The dynamic programming approach to finding subarrays with sum 0 is contributed by Vaibhav Saroj.
Time Complexity: O(n)
Auxiliary Space: O(n)
This article is contributed by Aditya Goel. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to contribute@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
