You are given an integer array, your task is to print all the possible sub-arrays with sum is equal to 0. So we need to Print all subarrays with 0 sum.
Table of Contents
Example
arr[] = {-2, 4, -2, -1, 1, -3, 1, 5, 7, -11, -6}Sub-Array found from 0 index to 2 index Sub-Array found from 0 index to 4 index Sub-Array found from 3 index to 4 index Sub-Array found from 1 index to 6 index Sub-Array found from 4 index to 9 index
Algorithm
- Find sum of array elements with some variable say “Sum” to keep a track of sub-array with sum 0.
- If Sum is found to be 0 it means possible sub-array is found from 0 to the current index.
- Check if Sum that is found from the above process, is present in our Map or not.
- If map contains the sum, it means it was the total sum of the previous sub-array and now it becomes the Sum of the element until the current indices.
- Insert current Sum into the Map if it was not already present.
Explanation
We are going to use hashing because, with this, we can maintain an eye on the sub-arrays and their indices. Also, we are going to use different collections. First, we have to find all the numbers in the array which forms the possible sub-arrays with sum 0. For that, we will add up the elements of the array and store it to sum. The sum was already being initialized at the start.
We will create a map that has the temporary sum as key and a vector as value. So, the vector here represents the indices at which the sum of elements from the start of input is equal to the current sum.
After this, we start traversing over the array. So, as we move forward we keep on adding the elements into a variable sum. If the sum is found to be 0 at any moment. So, this means that the sub-array from the start is 0. And also if have found some indices which had the sum equal to 0.
If the sum is not found to be zero. Then we check if the Map contains that sum. If the map doesn’t contain the calculated sum. Then there does not exist any subarray that ends at the current index and has sum 0. So, after finding all sub-arrays which end at the current index and have a sum equal to 0. We will add the current index to the vector in the map that has the current sum as the key.
But if Map contains the sum it means we found some previous sub-arrays that had the same sum. Then we need to add the value of that sum and indices.
And out of this, we return our list which we declared as a vector. From there if the return value has size 0 it means we found nothing else output will be printed.
C++ code to print all subarrays with 0 sum
#include<iostream>
#include<unordered_map>
#include<vector>
using namespace std;
vector< pair<int, int> > getSubArray(int arr[], int n)
{
unordered_map<int, vector<int> > Map;
vector <pair<int, int>> result;
int sum = 0;
for (int i = 0; i < n; i++)
{
sum += arr[i];
if (sum == 0)
result.push_back(make_pair(0, i));
if (Map.find(sum) != Map.end())
{
vector<int> vec = Map[sum];
for (auto val = vec.begin(); val != vec.end(); val++)
result.push_back(make_pair(*val + 1, i));
}
Map[sum].push_back(i);
}
return result;
}
void print(vector<pair<int, int>> result)
{
for (auto j= result.begin(); j != result.end(); j++)
cout << "Sub-Array found from " << j->first << " index to " << j->second <<" index"<< endl;
}
int main()
{
int arr[] = {-2, 4, -2, -1, 1, -3, 1, 5, 7, -11, -6};
int n = sizeof(arr)/sizeof(arr[0]);
vector<pair<int, int> > result = getSubArray(arr, n);
if (result.size() == 0)
cout << "No such Sub-array exists";
else
print(result);
return 0;
}
Sub-Array found from 0 index to 2 index Sub-Array found from 0 index to 4 index Sub-Array found from 3 index to 4 index Sub-Array found from 1 index to 6 index Sub-Array found from 4 index to 9 index
Java code to print all subarrays with 0 sum
import java.util.*;
class Pair
{
int start, end;
Pair(int a, int b)
{
start = a;
end = b;
}
}
class printSubArray0Sum
{
public static ArrayList<Pair> getSubArray(int[] arr, int n)
{
HashMap<Integer,ArrayList<Integer>> map = new HashMap<>();
ArrayList<Pair> temp = new ArrayList<>();
int sum = 0;
for (int i = 0; i < n; i++)
{
sum += arr[i];
if (sum == 0)
temp.add(new Pair(0, i));
ArrayList<Integer> list = new ArrayList<>();
if (map.containsKey(sum))
{
list = map.get(sum);
for (int j = 0; j < list.size(); j++)
{
temp.add(new Pair(list.get(j) + 1, i));
}
}
list.add(i);
map.put(sum, list);
}
return temp;
}
public static void print(ArrayList<Pair> result)
{
for (int i = 0; i < result.size(); i++)
{
Pair pair = result.get(i);
System.out.println("Sub-Array found from "+ pair.start + " index to " + pair.end+" index");
}
}
public static void main(String args[])
{
int[] arr = {-2, 4, -2, -1, 1, -3, 1, 5, 7, -11, -6};
int n = arr.length;
ArrayList<Pair> result = getSubArray(arr, n);
if (result.size() == 0)
System.out.println("No such Sub-array exists");
else
print(result);
}
}
Sub-Array found from 0 index to 2 index Sub-Array found from 0 index to 4 index Sub-Array found from 3 index to 4 index Sub-Array found from 1 index to 6 index Sub-Array found from 4 index to 9 index
Complexity Analysis
Time Complexity
O(n) where “n” is the number of elements in the array.
Space Complexity
O(n) where “n” is the number of elements in the array.