## 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 :**

`4`

**Example : 2**

`ar[] = [15,-2,2,-8,1,7,10,23]`

**Output :**

`5`

### Example 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`0`

sum. - Start traversing an array from the start.
- For every index
`i`

of the array, start a nested loop with variable`j`

that ranges from`i`

to 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
`0`

sum 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
`0`

sum 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 sum`0`

. - 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
`0`

sum problem’s solution is possible in $O(n)$ time and $O(n)$ space.