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++
#include <bits/stdc++.h>
using namespace std;
vector<pair< int , int > > findSubArrays( int arr[], int n)
{
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;
}
void 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;
}
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 > > output = findSubArrays(arr, n);
if (output.size() == 0) {
cout << "No subarray exists" ;
}
else {
print(output);
}
return 0;
}
|
Java
import java.io.*;
import java.util.*;
class Pair
{
int first, second;
Pair( int a, int b)
{
first = a;
second = b;
}
}
public class GFG
{
static ArrayList<Pair> findSubArrays( int [] arr, int n)
{
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;
}
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);
}
}
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 (out.size() == 0 )
System.out.println( "No subarray exists" );
else
print(out);
}
}
|
Python3
class Pair :
first = 0
second = 0
def __init__( self , a, b) :
self .first = a
self .second = b
class GFG :
@staticmethod
def findSubArrays( arr, n) :
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
@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
@staticmethod
def main( args) :
arr = [ 6 , 3 , - 1 , - 3 , 4 , - 2 , 2 , 4 , 6 , - 12 , - 7 ]
n = len (arr)
out = GFG.findSubArrays(arr, n)
if ( len (out) = = 0 ) :
print ( "No subarray exists" )
else :
GFG. print (out)
if __name__ = = "__main__" :
GFG.main([])
|
C#
using System;
using System.Collections.Generic;
class GFG
{
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;
}
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" );
}
public static void Main()
{
int [] arr = { 6, 3, -1, -3, 4, -2, 2, 4, 6, -12, -7 };
int n = arr.Length;
List<Tuple< int , int >> output = findSubArrays(arr, n);
if (output.Count == 0)
{
Console.WriteLine( "No subarray exists" );
}
else
{
print(output);
}
}
}
|
Javascript
function findSubArrays(arr, n)
{
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 print(out)
{
for (let it of out)
console.log( "Subarray found from Index " + it[0]
+ " to " + it[1]);
}
let arr = [ 6, 3, -1, -3, 4, -2, 2, 4, 6, -12, -7 ];
let n = arr.length ;
let out = findSubArrays(arr, n);
if (out.length == 0) {
console.log( "No subarray exists" );
}
else {
print(out);
}
|
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++
#include <bits/stdc++.h>
using namespace std;
vector< pair< int , int > > findSubArrays( int arr[], int n)
{
unordered_map< int , vector< int > > map;
vector <pair< int , int >> out;
int sum = 0;
for ( int i = 0; i < n; i++)
{
sum += arr[i];
if (sum == 0)
out.push_back(make_pair(0, i));
if (map.find(sum) != map.end())
{
vector< int > vc = map[sum];
for ( auto it = vc.begin(); it != vc.end(); it++)
out.push_back(make_pair(*it + 1, i));
}
map[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;
}
|
Java
import java.io.*;
import java.util.*;
class Pair
{
int first, second;
Pair( int a, int b)
{
first = a;
second = b;
}
}
public class GFG
{
static ArrayList<Pair> findSubArrays( int [] arr, int n)
{
HashMap<Integer,ArrayList<Integer>> map = new HashMap<>();
ArrayList<Pair> out = new ArrayList<>();
int sum = 0 ;
for ( int i = 0 ; i < n; i++)
{
sum += arr[i];
if (sum == 0 )
out.add( new Pair( 0 , i));
ArrayList<Integer> al = new ArrayList<>();
if (map.containsKey(sum))
{
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;
}
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);
}
}
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 (out.size() == 0 )
System.out.println( "No subarray exists" );
else
print(out);
}
}
|
Python3
def findSubArrays(arr,n):
hashMap = {}
out = []
sum1 = 0
for i in range (n):
sum1 + = arr[i]
if sum1 = = 0 :
out.append(( 0 , i))
al = []
if sum1 in hashMap:
al = hashMap.get(sum1)
for it in range ( len (al)):
out.append((al[it] + 1 , i))
al.append(i)
hashMap[sum1] = al
return out
def printOutput(output):
for i in output:
print ( "Subarray found from Index " +
str (i[ 0 ]) + " to " + str (i[ 1 ]))
if __name__ = = '__main__' :
arr = [ 6 , 3 , - 1 , - 3 , 4 , - 2 ,
2 , 4 , 6 , - 12 , - 7 ]
n = len (arr)
out = findSubArrays(arr, n)
if ( len (out) = = 0 ):
print ( "No subarray exists" )
else :
printOutput (out)
|
C#
using System;
using System.Collections.Generic;
class Pair
{
public int first, second;
public Pair( int a, int b)
{
first = a;
second = b;
}
}
class GFG
{
static List<Pair> findSubArrays( int [] arr, int n)
{
Dictionary< int , List< int >> map =
new Dictionary< int , List< int >>();
List<Pair> outt = new List<Pair>();
int sum = 0;
for ( int i = 0; i < n; i++)
{
sum += arr[i];
if (sum == 0)
outt.Add( new Pair(0, i));
List< int > al = new List< int >();
if (map.ContainsKey(sum))
{
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;
}
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);
}
}
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 (outt.Count == 0)
Console.WriteLine( "No subarray exists" );
else
print(outt);
}
}
|
Javascript
function findSubArrays(arr, n)
{
let map = {};
let out = [];
let sum = 0;
for ( var i = 0; i < n; i++)
{
sum += arr[i];
if (sum == 0)
out.push([0, i]);
if (map.hasOwnProperty(sum))
{
let vc = map[sum];
for (let it of vc)
out.push([it + 1, i]);
}
else
map[sum] = [];
map[sum].push(i);
}
return out;
}
function print(out)
{
for (let it of out)
console.log( "Subarray found from Index " + it[0] + " to " + it[1]);
}
let arr = [6, 3, -1, -3, 4, -2, 2, 4, 6, -12, -7];
let n = arr.length;
let out = findSubArrays(arr, n);
if (out.length == 0)
console.log( "No subarray exists" );
else
print(out);
|
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;
int sum = 0;
sums[0].push_back(-1);
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;
}
|
Java
import java.util.*;
public class Main {
public static List<Map.Entry<Integer, Integer>> findSubArrays( int [] arr, int n) {
List<Map.Entry<Integer, Integer>> out = new ArrayList<>();
Map<Integer, List<Integer>> sums = new HashMap<>();
int sum = 0 ;
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) {
out.add( new AbstractMap.SimpleEntry<>(j + 1 , i));
}
}
sums.computeIfAbsent(sum, k -> new ArrayList<>()).add(i);
}
return out;
}
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;
List<Map.Entry<Integer, Integer>> out = findSubArrays(arr, n);
if (out.size() == 0 ) {
System.out.println( "No subarray exists" );
} else {
print(out);
}
}
}
|
Python3
def find_subarrays(arr):
out = []
sums = { 0 : [ - 1 ]}
current_sum = 0
for i, num in enumerate (arr):
current_sum + = num
if current_sum in sums:
indices = sums[current_sum]
for j in indices:
out.append((j + 1 , i))
if current_sum in sums:
sums[current_sum].append(i)
else :
sums[current_sum] = [i]
return out
def 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 ]
subarrays = find_subarrays(arr)
if not subarrays:
print ( "No subarray exists" )
else :
print_subarrays(subarrays)
if __name__ = = "__main__" :
main()
|
C#
using System;
using System.Collections.Generic;
public class GFG
{
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 };
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;
}
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 findSubArrays(arr) {
const out = [];
const sums = new Map();
let sum = 0;
sums.set(0, [-1]);
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 print(out) {
for (const subarray of out) {
console.log(`Subarray found from Index ${subarray[0]} to ${subarray[1]}`);
}
}
function 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);
}
}
main();
|
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)
If you like GeeksforGeeks 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 GeeksforGeeks 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 geeks!