Problem Statement
Given the array $ar[]$ of size, $n$ has positive and negative integers. From the array $ar[]$, find the length of the largest subarray having a 0 sum.
As we have to find the length of the largest subarray. So, first of all, it is required to understand what is a subarray
Subarray :
A subarray of an array is defined as any contiguous sequence of elements of an array.
Example :
$[1,2,3,4]$
Subarrays of the above example :
$[1],[1,2],[1,2,3],[1,2,3,4],[2],[2,3],[2,3,4],[3],[3,4],[4]$
Example
Let us understand the largest subarray with the 0 sum problem with the examples.
Example : 1
ar[] = [4,-3,-6,5,1,6,8]Output :
4Example : 2
ar[] = [15,-2,2,-8,1,7,10,23]Output :
5Example Explanation
We are required to find all the subarrays starting from the ith index and ending with the jth index where $0<=i<n$ and $i<=j<n$ where $n$ represents the length of the array.
Example : 1
First of all, we will find the sum of every subarray of the input array $ar[]$.
Here the size of the array is 7 so we are required to find the sum of all the subarrays starting from the ith index and ending with the jth index where $0<=i<7$ and $i<=j<7$.
Refer to the below image for the explanation of Example1 :
Subarrays with 0 sum are : $[-6,5,1]$ with length 3 and $[4,-3,-6,5]$ with length 4.
So the maximum length of subarray with 0 sum is 4.
Example : 2
First, we will find the sum of every subarray of the input array ar[].
Here in the example, the size of the array is 8 so we are required to find the sum of all the subarrays starting from the ith index and ending with the jth index where $0<=i<8$ and $i<=j<8$.
Refer to the below image for the explanation of Example2 :
Subarrays with 0 sum are : $[-8,1,7]$ with length 3 , $[-2,2,-8,1,7]$ with length 5, $[2,-2]$ with length 2.
So the maximum length of subarray with a 0 sum is 5.
Input :
Given a positive integer n which represents the size of an array $ar[]$. And the n positive/negative integers represent the elements of $ar[]$.
Output :
You have to return the length of the largest subarray that has a sum of 0.
Constraints
The constraints for the largest subarray with a 0 sum problem are given below :
$1 <= n <= 100000$,
$-1000 <= ar[i] <= 1000$, for i in range 0 to $n$.
Approach 1 : Brute Force Approach – Using Three Nested Loops
Approach
We will consider all the subarrays of the input array and find the sum of every subarray and check the sum of every subarray. And then, store the length of the longest subarray among all the subarrays that have a sum of 0 and return the longest length as a result.
Algorithm
- Declare and initialize a variable max_length $= 0$, which stores the length of the largest subarray with
0sum. - Start traversing an array from the start.
- For every index
iof the array, start a nested loop with variablejthat ranges fromito the size of the array. - Initialize the variable cursum $= 0$ for storing the sum of subarray starting from the ith index and ending with the jth index.
- And then run a loop to find the sum of subarray starting with the ith index and ending with the jth index and store the sum in cursum.
- Check if the value of cursum is
0, then check if the length of the current subarray is greater than the length stored in max_length and update the max_length with the current subarray length $i.e.$ $j-i+1$. - Return the max_length.
Implementation
C++ Implementation :
// C++ program to find largest subarray length
// with sum 0
#include <iostream>
using namespace std;
// function for finding the length of the largest
// subarray of an array that has a sum 0
int maxLenSubSumZero(int ar[], int size){
// declaring the variable max_length for storing
// maximum length of subarray with sum 0
int max_length = 0;
// iterating over the input array
for(int i=0;i<size;i++){
for(int j=i;j<size;j++){
// variable cursum to store the sum of subarray
// that starts with ith index and ends with a jth index
int cursum = 0;
for(int k=i;k<=j;k++)
cursum = cursum + ar[k];
// checks that the subarray has a sum zero or not
if(cursum == 0)
{
// if the sum of the subarray is zero and
// current subarray length is greater
// then update max_length
if(max_length < j-i+1)
max_length = j-i+1;
}
}
}
//returning the length of the largest subarray with a sum 0
return max_length;
}
//driver code
int main(){
//declaring an array
int ar[]={15,-2,2,-8,1,7,10,23};
//finding the size of an array
int size=sizeof(ar)/sizeof(ar[0]);
// calling function
int res=maxLenSubSumZero(ar,size);
//printing result
cout<<res;
}
Output :
5
Java Implementation :
// java program to find the largest subarray length with a sum 0
class FindMaxLenSub{
// function for finding the length of the largest
// subarray of an array that has a sum of 0
static int maxLenSubSumZero(int ar[], int size){
// declaring the variable max_length for storing
// maximum length of subarray with sum 0
int max_length = 0;
// iterating over the input array
for(int i=0;i<size;i++){
for(int j=i;j<size;j++){
// variable cursum to store the sum of subarray
// that starts with ith index and ends with a jth index
int cursum = 0;
for(int k=i;k<=j;k++)
cursum = cursum + ar[k];
// checks that the subarray has a sum of zero or not
if(cursum == 0){
// if the sum of the subarray is zero and
// current subarray length is greater
// then update max_length
if(max_length < j-i+1)
max_length = j-i+1;
}
}
}
//returning the length of the largest subarray with a sum of 0
return max_length;
}
public static void main(String args[]){
//declaring an array
int[] ar={15,-2,2,-8,1,7,10,23};
//finding the size of an array
int size=ar.length;
// calling function
int res=maxLenSubSumZero(ar,size);
//printing result
System.out.println(res);
}
}
Output :
5
Python Implementation :
# Python program to find largest subarray length with sum 0
# function for finding the length of
# largest subarray of an array that has a sum of 0
def maxLenSubSumZero(ar):
# declaring the variable max_length for storing
# maximum length of subarray with sum 0
max_length = 0
#iterating over the input array
for i in range(len(ar)):
for j in range(i, len(ar)):
cursum=0
for k in range(i,j+1):
# variable cursum to store the sum of subarray
# that starts with ith index and ends with a jth index
cursum += ar[k]
# checks that the subarray has a sum zero or not
if cursum == 0:
# if the sum of the subarray is zero
# and current subarray length is greater
# then update max_length
max_length = max(max_length, j-i+1)
# returning the length of the largest subarray with a sum 0
return max_length
#declaring an array
ar = [15, -2, 2, -8, 1, 7, 10, 13]
# calling function
res=maxLenSubSumZero(ar)
# printing result
print(res)
Output :
5
Time Complexity
As we run three nested loops one loop for starting index of the subarray, the second loop for the ending index of the subarray, and the third loop for finding the sum of the current subarray. So worst case time complexity of running three nested loops is $O(n^{3})$.
So worst case time complexity of this approach is $O(n^{3})$.
Space Complexity
We are not using the extra space. So worst case space complexity of this approach is $O(1)$.
Approach 2 : Efficient Brute Force – Using Two Nested Loops
Approach
This approach is an optimized version of the previous approach. In this approach, we use the brute force approach, where two nested loops are used to calculate the subarrays running sum. In two loops, the outer loop is to fix the starting index of a subarray, and the inner loop is for the ending index of the subarray while iterating the second loop, we will find the sum and store the length of the largest subarray with 0 sum.
Algorithm
- Declare and Initialize a variable max_length $= 0$, which will store the length of the largest subarray with the sum
0. - Start traversing the array from starting index and initialize the variable cur_sum $= 0$ which will store the sum of the subarray starting from the ith index.
- Traverse array from next element of current index till the end of th array and at every iteration add the current element to cur_sum.
- Now check if cur_sum $= 0$, and check if max_length $<$ current subarray length, then update the value of max_length with current subarray length.
- After traversing the whole array return max_length as the result.
Implementation
C++ Implementation :
// C++ program to find largest subarray length with sum 0
#include <iostream>
using namespace std;
// function for finding the length of the largest
// subarray of an array that has sum 0
int maxLenSubSumZero(int ar[], int size){
// declaring the variable max_length for storing
// maximum length of subarray with sum 0
int max_length = 0;
// iterating over the input array
for(int i=0;i<size;i++){
// variable cursum to store the current sum of subarray
// starting with ith index
int cursum=0;
for(int j=i;j<size;j++){
// getting the sum of subarray
// that starts with i and ends with j
cursum = cursum + ar[j];
// checks that the subarray has sum zero or not
if(cursum == 0)
{
// if sum of subarray is zero
// and current subarray length is greater
// then update max_length
if(max_length < j-i+1)
max_length = j-i+1;
}
}
}
//returning the length of largest subarray with sum 0
return max_length;
}
//driver code
int main(){
//declaring an array
int ar[]={15,-2,2,-8,1,7,10,23};
//finding size of an array
int size=sizeof(ar)/sizeof(ar[0]);
// calling function
int res=maxLenSubSumZero(ar,size);
//printing result
cout<<res;
}
Output :
5
Java Implementation :
// java program to find largest subarray length with sum 0
class FindMaxLenSub{
// function for finding the length of largest
// subarray of an array that has sum 0
static int maxLenSubSumZero(int ar[], int size){
// declaring the variable max_length for storing
// maximum length of subarray with sum 0
int max_length = 0;
// iterating over the input array
for(int i=0;i<size;i++){
// variable cursum to store the current sum of subarray
// starting with ith index
int cursum=0;
for(int j=i;j<size;j++){
// getting the sum of subarray that starts with i and ends with j
cursum = cursum + ar[j];
// checks that the subarray has sum zero or not
if(cursum == 0){
// if sum of subarray is zero and
// current subarray length is greater
// then update max_length
if(max_length < j-i+1)
max_length = j-i+1;
}
}
}
//returning the length of largest subarray with sum 0
return max_length;
}
public static void main(String args[]){
//declaring an array
int[] ar={15,-2,2,-8,1,7,10,23};
//finding size of an array
int size=ar.length;
// calling function
int res=maxLenSubSumZero(ar,size);
//printing result
System.out.println(res);
}
}
Output :
5
Python Implementation :
# Python program to find largest subarray length with sum 0
# function for finding the length of
# largest subarray of an array that has sum 0
def maxLenSubSumZero(ar):
# declaring the variable max_length for storing
# maximum length of subarray with sum 0
max_length = 0
#iterating over the input array
for i in range(len(ar)):
#variable cursum to store the current sum of subarray
#starting with ith index
cursum=0
for j in range(i, len(ar)):
# getting the sum of subarray
# that starts with i and ends with j
cursum += ar[j]
# checks that the subarray has sum zero or not
if cursum == 0:
# if sum of subarray is zero and
# current subarray length is greater
# then update max_length
max_length = max(max_length, j-i+1)
# returning the length of largest subarray with sum 0
return max_length
#declaring an array
ar = [15, -2, 2, -8, 1, 7, 10, 13]
# calling function
res=maxLenSubSumZero(ar)
# printing result
print(res)
Output :
5
Time Complexity
As we are running two nested loops, one loop for starting index of the subarray, the second loop for the ending index of the subarray, and while running the second loop, we are also calculating the running sum of the subarray.
We know that worst case time complexity of running two nested loops is $O(n^{2})$.
So worst case time complexity of this approach is $O(n^{2})$.
Space Complexity
We are not using the extra space. So worst case space complexity of this approach is $O(1)$.
Approach 3 : Alternative and Efficient Approach – Using the Hash Table
Approach
In this approach to the largest subarray with the 0 sum problem, we are using hashing for finding the length of the largest subarray. The idea of this approach is to iterate over the input array and calculate the sum of elements from starting element to the current element. And check if the current sum is present in the map, then there is a subarray with a 0 sum.
Algorithm
- Initialize max_length $= 0$, cur_sum $= 0$ and create an empty map for storing the previous sum-index as a key-value pair.
- Iterate over the input array.
- At every index update sum by adding current element cur_sum $=$ cur_sum $+$ $array[i]$.
- For every index, check if the cur_sum is on the map or not.
- If the cur_sum is present in the map, then update the max_length to a maximum max_length and the difference between two indices (current index and index in the hash-map).
- Otherwise, put the cur_sum as a key in the map with the index as a value.
- Return the maximum length (max_length).
Implementation
C++ Implementation :
// c++ program to find largest subarray length with sum 0
#include <bits/stdc++.h>
using namespace std;
// function for finding the length of
// largest subarray of an array that has sum 0
int maxLenSubSumZero(int ar[], int size)
{
// Creating the map for storing previous sums
unordered_map<int, int> prevsummap;
// Declaring and Initializing the cur_sum to store sum
int cur_sum = 0;
// declaring the variable max_length for storing
// maximum length of subarray with sum 0
int max_length = 0;
// Iterate over the input array
for (int i = 0; i < size; i++) {
// Adding current element to the previous calculated sum
cur_sum += ar[i];
if (ar[i] == 0 && max_length == 0)
max_length = 1;
if (cur_sum == 0)
max_length = i + 1;
// Checking this sum in the map
if (prevsummap.find(cur_sum) != prevsummap.end()) {
// If sum is in map then update the value of max_length
max_length = max(max_length, i - prevsummap[cur_sum]);
}
else {
// If sum is not in the map then
// insert it into map with current index
prevsummap[cur_sum] = i;
}
}
return max_length;
}
//driver code
int main(){
//declaring an array
int ar[]={15,-2,2,-8,1,7,10,23};
//finding size of an array
int size=sizeof(ar)/sizeof(ar[0]);
// calling function
int res=maxLenSubSumZero(ar,size);
//printing result
cout<<res;
}
Ouput :
5
Java Implementation :
// A Java program to find maximum length subarray with 0 sum
import java.util.HashMap;
// java program to find largest subarray length with sum 0
class FindMaxLenSub{
// function for finding the length of largest
// subarray of an array that has sum 0
static int maxLenSubSumZero(int ar[], int size){
// declaring the variable max_length for storing
// maximum length of subarray with sum 0
int max_length = 0;
// Creating an empty hashmap for storing previous sum
HashMap<Integer,Integer> prevsummap=new HashMap<Integer, Integer>();
// Declaring and Initializing the cur_sum to store sum
int cur_sum = 0;
// iterating over an input array
for (int i = 0; i < ar.length; i++) {
// Adding current element to the previous calculated sum
cur_sum += ar[i];
if (ar[i] == 0 && max_length == 0)
max_length = 1;
if (cur_sum == 0)
max_length = i + 1;
// Checking this sum in the map
Integer prevind = prevsummap.get(cur_sum);
// If sum is in map then update the value of max_length
if (prevind != null)
max_length = Math.max(max_length, i - prevind);
else {
// If sum is not in the map
// then insert it into map with current index
prevsummap.put(cur_sum, i);
}
}
//returning the length of largest subarray with sum 0
return max_length;
}
public static void main(String args[]){
//declaring an array
int[] ar={15,-2,2,-8,1,7,10,23};
//finding size of an array
int size=ar.length;
// calling function
int res=maxLenSubSumZero(ar,size);
//printing result
System.out.println(res);
}
}
Ouput :
5
Python Implementation :
# Python program to find largest subarray length with sum 0
# function for finding the length of
# largest subarray of an array that has sum 0
def maxLenSubSumZero(ar):
# declaring the variable max_length for storing
# maximum length of subarray with sum 0
max_length = 0
# Initializing the cur_sum to store sum
cur_sum = 0
# NOTE: Hash Map can be implemented by dictionary in python
# Creating an empty hashmap(dictionary) for storing previous sum
prevsummap = {}
# iterating over an input array
for i in range(len(ar)):
# Adding current element to the previous calculated sum
cur_sum += ar[i]
if ar[i] == 0 and max_length == 0:
max_length = 1
if cur_sum == 0:
max_length = i + 1
# NOTE: 'in' operator is used to search key in dictionary
# Check if sum is in map
# then update the value of max_length
if cur_sum in prevsummap:
max_length = max(max_length, i - prevsummap[cur_sum] )
else:
# If sum is not in the map then insert it into map with current index
prevsummap[cur_sum] = i
return max_length
#declaring an array
ar = [15, -2, 2, -8, 1, 7, 10, 13]
# calling function
res=maxLenSubSumZero(ar)
# printing result
print(res)
Ouput :
5
Time Complexity
As we are iterating over an input array of size n once whose time complexity $O(n)$ and while iterating, we are searching/inserting an element in the map whose time complexity is $O(1)$. So total time complexity of this approach is $O(n)*O(1)$.
So worst case time complexity of this approach is $O(n)$.
Space Complexity
As we are using a hashmap for storing the previous sums. So worst case space complexity of this approach is $O(n)$.
Comparison of Different Solutions
Comparison of time and space complexity of all approaches of solution of largest subarray with 0 sum problem is given below :
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Brute Force Approach – using three nested loops | $O(n^{3})$ | $O(1)$ |
| Efficient Brute Force – using two nested loops | $O(n^{2})$ | $O(1)$ |
| Alternative and Efficient Approach – using hash table | $O(n)$ | $O(n)$ |
Conclusion
- In the largest subarray with the
0sum problem, we need to find the size of the longest subarray among all the subarrays, which has a sum of 0. - Subarray is the contiguous sequence of the elements of the input array.
- In the largest subarray with the
0sum problem, we are given the size of the array and the elements of an array as an input and we are required to return the length of the largest subarray with sum0. - Brute Force Approach to this problem finds the length of the largest subarray using three loops and time its time complexity is $O(n^{3})$.
- Efficient Brute Force Approach to this problem finds the length of the largest subarray using two loops and time its time complexity is $O(n^{2})$.
- With the help of hashing, the length of the largest subarray with a
0sum problem’s solution is possible in $O(n)$ time and $O(n)$ space.
