Problem Statement
Given an integer array where the array has both negative and positive values, print all the subarrays from the given array whose sum is zero.
Example
Let’s consider the below-given integer array:
Input : arr = [0, -1, 8, -5, -3, -7, 4, 2, 1]
Output for the given array is:
Zero-sum Subarray is from 0 to 0
Zero-sum Subarray is from 2 to 4
Zero-sum Subarray is from 2 to 8
Zero-sum Subarray is from 5 to 8Explanation
Subarrays formed are clearly shown in the figure:
- Subarrays from the following start and end indices give zero sum subarray:
- $0^{th}$ index to $0^{th}$ index:
- Elements present: $[0]$
- Subarray sum obtained is: $0$.
- $2^{nd}$ index to $4^{th}$ index:
- Elements present: $[8, -5, -3]$
- Subarray sum obtained is: $8 + (-5) + (-3) = 0$.
- $2^{nd}$ index to $8^{th}$ index:
- elements present: $[8, -5, -3, -7, 4, 2, 1]$
- Subarray sum obtained is: $8 + (-5) +(-3) + (-7) + 4 + 2 + 1 = 0$.
- $5^{th}$ index to $8^{th}$ index:
- elements present: $[-7, 4, 2, 1]$
- Subarray sum obtained is: $(-7) + 4 + 2 + 1 = 0$.
Therefore, from these starting indices to the ending indices it indicates that the sum of subarrays is zero.
Constraints
- $1 ~<=~ N~ (Length~ of~ the~ input~ array)~ <=10^5$
- $-10^6~ <=~ arr[i]~ <=~ 10^6$
- All the elements in the array are integers
Approach 1
We can say that for N number of elements in the given array, the number of subarrays possible is:
$$
\dfrac{N*(N+1)}{2}
$$
But we only need to find the subarrays whose sum is zero. Our brute force approach can be generating all the subarrays and to check whether the subarray generated has a sum that is equal to zero. If the subarray’s sum is zero then we will print the starting and ending index of the subarray which is formed.
Below is the algorithm which clearly explains the approach.
Algorithm
- Firstly we need to generate all the subarrays. For generating subarrays we use two nested loops.
- The first loop with the iterator, i which starts from $0^{th}$ index to the last index of the array.
- Initialise the sum variable which keeps track of the subarray sum until that time.
- The second loop starts with iterator j, starts from $i^{th}$ index to the last index of the array.
- After computing the subarrays, we need to calculate their respective sum and check whether the subarray sum is zero.
- For computing the sum of each subarray we need to run a loop for all the elements present in the subarray.
- Instead of creating all the subarrays stored in one data structure and later checking for the zero-sum of the subarray, we can just keep track of the sum of the subarray using a variable in the second loop, this is considered to be a more efficient approach for both in space and in time complexities wise.
- Every time increment the subarray sum with the value of the element present at $j^{th}$ index and check whether it is zero or not.
- If the subarray sum is obtained to be zero, we need to print the i and $j^{th}$ indices in the output.
Implementation
Below is the implementation of this approach in C++, Python, and Java:
C++ implementation of Zero subarray sum using brute force:
// C++ program for subarray sum
#include <iostream>
#include <unordered_map>
using namespace std;
// Main function which prints all the subarrays whose sum is zero
void ZeroSubarraySum(int arr[], int N){
// We need two nested loops
// First loop starts from 0th index to the end of the array
for (int i = 0; i < N; i++){
// initialize the sum to zero
int subarraysum = 0;
// Here i is the start index of the subarray, j is the end index of the subarray
for (int j = i; j < N; j++){
// Compute the sum from ith index to jth index
subarraysum += arr[j];
// After computing the sum, check whether it is zero.If zero print the output
if (subarraysum == 0) {
cout << "Zero-sum subarray sum is from " << i << " to " << j << " \n";
}
}
}
}
// Driver Code
int main(){
// given set of input integer array
int arr[] = { 0, -1, 8, -5, -3, -7, 4, 2, 1 };
int N = sizeof(arr)/sizeof(arr[0]);
// main function for printing all subarrays with zero sum
ZeroSubarraySum(arr, N);
return 0;
}
Output for the given array is:
Zero-sum subarray sum is from 0 to 0
Zero-sum subarray sum is from 2 to 4
Zero-sum subarray sum is from 2 to 8
Zero-sum subarray sum is from 5 to 8
Python implementation of Zero subarray sum using brute force:
# Python program of zero subarray sum
# Main function which prints all the subarrays whose sum is zero
def ZeroSubarraySum(arr):
# We need two nested loops
# First loop starts from 0th index to the end of the array
for i in range(len(arr)):
#intialise the sum to zero
subarraysum = 0
# Here i is the start index of the subarray, j is the end index of the subarray
for j in range(i, len(arr)):
# Compute the sum from ith index to jth index
subarraysum += arr[j]
# After computing the sum, check whether it is zero.If zero print the output
if subarraysum == 0:
print('Zero-sum Subarray is from '+ str(i)+ " to " +str(j))
# Driver Code
if __name__ == '__main__':
# Input the integer array
arr = [0, -1, 8, -5, -3, -7, 4, 2, 1]
# Call the function which prints the zero subarray sum
ZeroSubarraySum(arr)
Output for the given array is:
Zero-sum Subarray is from 0 to 0
Zero-sum Subarray is from 2 to 4
Zero-sum Subarray is from 2 to 8
Zero-sum Subarray is from 5 to 8
Java implementation of Zero subarray sum using brute force:
// Java program for subarray sum equal to zero
class Solution{
import java.io.*;
import java.util.*;
public class Solution {
public static void ZeroSubarraySum(int[] arr){
// We need two nested loops
// First loop starts from 0th index to the end of the array
for (int i = 0; i < arr.length; i++){
// initialize the sum to zero
int subarraysum = 0;
// Here i is the start index of the subarray, j is the end index of the subarray
for (int j = i; j < arr.length; j++){
// Compute the sum from ith index to jth index
subarraysum += arr[j];
// After computing the sum, check whether it is zero.If zero print the output
if (subarraysum == 0) {
System.out.println("Zero-sum subarray sum is from " + i + " to " + j);
}
}
}
}
// Driver code
public static void main (String[] args){
// given set of input integer array
int[] arr = { 0, -1, 8, -5, -3, -7, 4, 2, 1 };
// main function for printing all subarrays with zero sum
ZeroSubarraySum(arr);
}
}
Output for the given array is:
Zero-sum Subarray is from 0 to 0
Zero-sum Subarray is from 2 to 4
Zero-sum Subarray is from 2 to 8
Zero-sum Subarray is from 5 to 8
Explanation:
We can observe that the subarrays from the start index and end index from the output have the subarray sum which is zero. All the subarrays whose sum is zero are being printed by indicating the starting and ending index of the subarray which is formed.
Complexity Analysis
Time Complexity: $O(N^2)$ where N is the length of the input integer array.
- For generating the $(N*\frac{(N+1)}{2})$ number of subarrays, it takes time complexity of $O(N^2)$ because we consider the starting index of the subarrays can be from the 0th index and the ending index can go upto last index of the array.
- The ending index of any subarray can be from the $i^{th}$ index to any index in the array which is larger or equal to i.
- For computing the sum of each subarray and checking whether it is equal to zero, it takes a time complexity of $O(1)$.
- Therefore the overall time complexity of a zero-sum subarray using brute force is $O(N^2)$.
Space Complexity: O(1)
- It doesn’t need any of extra space as we are updating the value of the subarray and also keeping track of the sum of the subarray using a variable.
Approach 2: (Using Hashing)
In the above approach, we generate all the possible subarrays of the given integer array and check whether its sum is zero. Instead of this, we can use hashing for solving the zero subarray sum. In this approach, we store the sum of all the subarrays starting from the $0^{th}$ index to the current index using a hash map. If we encounter the sum of the subarray calculated as zero we print the output giving the starting index as 0 and the ending index as the current index.
If the sum computed is already present in the hashmap, it indicates that there is already a subarray from nums[0] to the current index i.e, nums[i], and now the same sum is obtained for the current subarray which means the sum of the subarray is zero.
Algorithm:
For all the elements in the given integer input array follow the below-mentioned steps:
- Compute the sum of elements till the current index and store it in
subarray_sum. - If the
subarray_sumcomputed is zero, then it means that we have found a subarray with zero-sum starting from $0^{th}$ index to the current index i.e, $i^{th}$ index. - And also if the
subarray_sumis already present in the hashmap then it indicates that thesubarray_sumwas the sum of some subarray i.e, which starts fromnums[0]tonums[i]as in the above example. - Now the same sum is obtained for the current subarray which is computed and it means that it is the same as the sum of the subarray from
nums[0]tonums[j], (where j is the previous index where the current sum is already found) which means that the sum of the subarraynums[i+1]tonums[j]must also be0. - We store all the starting index and ending index of the zero-sum subarray in the data structure like array or vector, etc.
- And at last we need to add the current sum to the hashmap.
Example
Let’s consider the below example as the input integer array:
Input :
arr = [0, -1, 8, -5, -3, -7, 4, 2, 1]
Firstly, declare the hashmap and answer array where we store the starting and ending index. All the steps to be followed to find the zero-sum subarray using hashing is clearly shown in the below image:
Output for the given array is:
Zero-sum Subarray is from 0 to 0
Zero-sum Subarray is from 2 to 4
Zero-sum Subarray is from 2 to 8
Zero-sum Subarray is from 5 to 8
Explanation: We can observe that the subarrays from the start index and end index from the output have the subarray sum which is zero. All the subarrays whose sum is zero are being printed by indicating the starting and ending index of the subarray which is formed.
Implementation
Below is the implementation of this approach using hashing in C++, python, and java.
C++ implementation of zero subarray sum using hashing:
// C++ program for finding the subarrays whose sum is zero
#include <bits/stdc++.h>
using namespace std;
// Main function required for printing all the zero subarray sum
vector< pair<int, int> > ZeroSubarraySum(int nums[], int N){
// A hashtable is created which is used to store current subarray sum
unordered_map<int, vector<int> > hashtable;
// to store the starting and ending indices store the indices in the ans array
vector <pair<int, int>> ans;
// helps in computing the sum of elements
int currentsum = 0;
for (int i = 0; i < N; i++){
// add the value of nums[i] to the current sum
currentsum += nums[i];
// if the current sum is zero then it means that there is a zero subarray sum with starting index as 0 and ending index as the current index.
if (currentsum == 0)
// append the values of indices into the ans array
ans.push_back(make_pair(0, i));
// If sum already exists in the hashtable then there exists at-least one subarray which is ending at index i with zero subarray sum
if (hashtable.find(currentsum) != hashtable.end()){
// map[sum] stores starting index of all subarrays
vector<int> ans1 = hashtable[currentsum];
for (auto k = ans1.begin(); k != ans1.end(); k++)
ans.push_back(make_pair(*k + 1, i));
}
// Important - no else
hashtable[currentsum].push_back(i);
}
// return output vector
return ans;
}
// Driver code
int main()
{
int nums[] = { 0, -1, 8, -5, -3, -7, 4, 2, 1 };
int N = sizeof(nums)/sizeof(nums[0]);
vector<pair<int, int> > ans = ZeroSubarraySum(nums, N);
// if we didn’t find any subarray with 0 sum,
// then subarray doesn’t exists
if (ans.size() == 0)
cout << "No subarray exists";
else
for (auto k = ans.begin(); k != ans.end(); k++)
cout << "Subarray found from Index " <<
k->first << " to " << k->second << endl;
return 0;
}
Output for the given array is:
Zero-sum Subarray is from 0 to 0
Zero-sum Subarray is from 2 to 4
Zero-sum Subarray is from 2 to 8
Zero-sum Subarray is from 5 to 8
Python implementation of zero subarray sum using hashing:
# Python program for printing the subarrays whose sum is zero using hashing
def ZeroSubarraySum(nums,N):
# A hashtable is created which is used to store current subarray sum
hashtable = {}
# to store the starting and ending indices store the indices in the ans array
ans = []
# helps in computing the sum of elements
currentsum = 0
for i in range(N):
# add the value of nums[i] to the current sum
currentsum += nums[i]
# if the current sum is zero then it means that there is a zero subarray sum with starting index as 0 and ending index as the current index.
if currentsum == 0:
# append the values of indices into the ans array
ans.append((0, i))
ans1 = []
# If sum already exists in the hashtable then there exists at-least one subarray which is ending at index i with zero subarray sum
if currentsum in hashtable:
# this helps in storing the indices
ans1 = hashtable.get(currentsum)
for k in range(len(ans1)):
ans.append((ans1[k] + 1, i))
ans1.append(i)
hashtable[currentsum] = ans1
return ans
# Driver Code
if __name__ == '__main__':
# Input the integer array
nums = [0, -1, 8, -5, -3, -7, 4, 2, 1]
# Call the function which prints the zero subarray sum
ans = ZeroSubarraySum(nums, len(nums))
# if there is no subarray whose sum is zero return not present
if (len(ans) == 0):
print ("No subarray with zero-sum is present")
# else print the subarrays whose sum is zero
else:
for i in ans:
print ("Zero sum subarray is from " + str(i[0]) + " to " + str(i[1]))
Output for the given array is:
Zero-sum Subarray is from 0 to 0
Zero-sum Subarray is from 2 to 4
Zero-sum Subarray is from 2 to 8
Zero-sum Subarray is from 5 to 8
Java implementation of zero subarray sum using hashing:
// java program for printing the subarray start and end indices whose sum is zero
import java.io.*;
import java.util.*;
// Pair class defined for storing and extracting indices
class Pair
{
int first, second;
Pair(int a, int b)
{
first = a;
second = b;
}
}
// Main class
public class Solution{
// Main function required for printing all the zero subarray sum
static ArrayList<Pair> ZeroSubarraySum(int[] nums, int N){
// A hashtable is created which is used to store current subarray sum
HashMap<Integer,ArrayList<Integer>> hashtable = new HashMap<>();
//to store the starting and ending indices store the indices in the ans array
ArrayList<Pair> ans = new ArrayList<>();
// helps in computing the sum of elements
int currentsum = 0;
for (int i = 0; i < N; i++){
// add the value of nums[i] to the current sum
currentsum += nums[i];
// if the current sum is zero then it means that there is a zero subarray sum with starting index as 0 and ending index as the current index.
if (currentsum == 0)
// append the values of indices into the ans array
ans.add(new Pair(0, i));
ArrayList<Integer> ans1 = new ArrayList<>();
// If sum already exists in the hashtable then there exists at-least one subarray which is ending at index i with zero subarray sum
if (hashtable.containsKey(currentsum)){
// this helps in storing the indices
ans1 = hashtable.get(currentsum );
for (int k = 0; k < ans1.size(); k++){
ans.add(new Pair(ans1.get(k) + 1, i));
}
}
ans1.add(i);
hashtable.put(currentsum , ans1);
}
return ans;
}
// Utility function needed to print all the subarrays starting and ending indices whose sum is zero
static void Print_Ans(ArrayList<Pair> ans){
for (int it = 0; it < ans.size(); it++){
Pair k = ans.get(it);
System.out.println("Zero sum subarray is from " + k.first + " to " + k.second);
}
}
// Driver code
public static void main (String[] args){
// given set of input integer array
int[] nums = { 0, -1, 8, -5, -3, -7, 4, 2, 1 };
int N= nums.length;
// main function for printing all subarrays with zero sum
ArrayList<Pair> ans = ZeroSubarraySum(nums, N);
// if there is no subarray whose sum is zero return not present
if (ans.size() == 0)
System.out.println("No subarray exists");
else
// else print the subarrays whose sum is zero
Print_Ans(ans);
}
}
Output for the given array is:
Zero-sum Subarray is from 0 to 0
Zero-sum Subarray is from 2 to 4
Zero-sum Subarray is from 2 to 8
Zero-sum Subarray is from 5 to 8
Explanation:
We can observe that the subarrays from the start index and end index from the output have the subarray sum which is zero. All the subarrays whose sum is zero are being printed by indicating the starting and ending index of the subarray which is formed.
Complexity Analysis
Time Complexity: O(N) where N is the length of the input integer array.
- We can find all the subarrays with sum equal to zero in one single traversal using a hashtable.
- For each lookup in hashmap i.e, for checking whether the current sum is present already in the hashmap or not takes the time complexity of O(log N) and for computing the current sum it takes constant time i.e, O(1).
- Therefore the overall time complexity obtained for zero subarray sum is O(N) if hashmap is used for storing the subarray sums.
Space Complexity: O(N) where N is the length of the input integer array.
- This extra space is needed for the hashmap to store the current sum values during the computation of the zero-sum subarray.
Conclusion
- In this article we have discussed two approaches for finding the zero subarray sum from the given set of elements.
- In the first approach, it is a brute force approach where we use two nested loops to compute the subarrays and find the sum and check whether it is zero or not.
- This method has a time complexity of $O(N^2)$, where N is the length of the integer input array and a space complexity of
O(1). - In the second method we use hashing, where we store the current computed subarray sum in it.
- This method has a time complexity of
O(N), where N is the length of the integer input array, and has a space complexity ofO(N)which is used for a hashmap.
