Length of the Largest Subarray with Zero Sum

Difficulty: Medium, Asked-in: Microsoft, Amazon

Key takeaway: An excellent problem to learn problem-solving using a hash table.

Let’s understand the problem!

Given an array X[] of n integer elements, write a program to find the length of the longest subarray with a sum equal to 0. In general, for all j > i, find max (j - i + 1) among all subarray with zero-sum. Note: the length of a subarray starting from index i and ending at index j = j - i + 1.

Example 1

Input: X[] = [14, -1, 1, -6, 1, 5, 12, 17], Output: 5

Explanation: The longest sub-array with elements summing up to 0 is [-1, 1, -6, 1, 5].

Example 2

Input: X[] = [1, 5, 10], Output: 0

Explanation: There is no subarray with 0 sum.

Example 3

Input: X[] = [1, 0, 2], Output: 1

Explanation: The longest sub-array with elements summing up to 0 is [0]

Discussed solution approaches

A brute force approach using three nested loops
A solution approach using two nested loops
An efficient approach using a hash table

Solution approach 1: A brute force idea using three nested loops

Solution idea and steps

A basic solution would be to explore all possible subarrays, calculate the sum of each subarray and track the maximum length of the subarray with zero-sum using a variable.

We initialize a variable maxZeroSubarray to track the maximum length of the subarray with zero-sum.
Now we run two nested loops to generate all pairs of indices i.e. (i, j), where i <= j. Here outer loop will run from i = 0 to n - 1 and inner loop will run from j = i to n - 1.
Inside the nested loop, we run another loop from k = i to j to calculate the sub-array sum between indices (i, j). We store this sum in a variable subarraySum.
When we find any sub-array sum equal to zero i.e. if(subarraySum == 0), we update the maximum length found so far i.e. if (maxZeroSubarray < j - i + 1), maxZeroSubarray = j - i + 1. Here the length of each subarray is j - i + 1. Think!
After exploring the sum of all subarrays, we return the value stored in the variable maxZeroSubarray.

Solution pseudocode

int largestSubarrayZeroSum(int X[], int n)
{
    int maxZeroSubarray = 0
    for (int i = 0, i < n; i = i + 1)
    {
        for (int j = i; j < n; j = j + 1) 
        {   
            int subarraySum = 0
            for (int k = i; k <= j; k = k + 1)
                subarraySum = subarraySum + X[k]
            
            if (subarraySum == 0)
            {
                if (maxZeroSubarray < j - i + 1)
                    maxZeroSubarray = j - i + 1
            }      
        }
    }
    return maxZeroSubarray
}

Solution Analysis

We are running three nested loops. So, time complexity in the worst case = O(n³). Note: Explore the last part of this blog to understand the analysis: analysis of loop in programming.
We are using constant extra space. Space complexity = O(1)

Solution approach 2: An optimized solution using two nested loops

Solution idea

Now the critical question is: can we further optimize the time complexity of the above approach? Can we avoid the inner loop from k = i to j for calculating the subarray sum? Let's think!

The idea is: if we know the sub-array sum from i to j, we can easily find the sub-array sum from i to j + 1 in O(1). Subarray sum from i to j + 1 = Subarray sum from i to j + X[j + 1]. Think!

Here outer loop from i = 0 to n - 1 picks the starting index, and the inner loop from j = i to n - 1 calculates the running sum of all sub-arrays starting from the index i.
Inside the inner loop, if the sum comes out to be zero, we find its length and update the max length found so far. This is the optimized version of the above approach, where we are running two nested loops and exploring the sub-array starting at all positions in the array.

Solution pseudocode

int largestSubarrayZeroSum(int X[], int n)
{
    int maxZeroSubarray = 0
    for (int i = 0, i < n; i = i + 1)
    {
        int subarraySum = 0
        for (int j = i; j < n; j = j + 1)
        {
            subarraySum = subarraySum + X[i]
            if (subarraySum == 0)
                maxZeroSubarray = max(maxZeroSubarray, j - i + 1)
        }        
    }
    return maxZeroSubarray
}

Solution analysis

We are running two nested loops to explore each subarray from (i, j), where i <= j.
Total number of loop iteration = n + (n - 1) + .... + 2 + 1 = n(n + 1)/2 = O(n^2)
At each iteration, we are doing O(1) operations. So time complexity = The total number of nested loops iteration * O(1) = O(n^2) * O(1)
We are using constant extra space. Space complexity = O(1)

Solution approach 3: An efficient idea using a hash table

Solution idea

The critical question is: can we improve the time complexity to O(n)? Can we solve this problem in a single loop by using some insights from the problem? Let’s think!

Suppose sum(i, j) is the sub-array sum from the index i to j where i < j. Here we can identify two properties related to sum(i, j).

Continuous sum of elements from i to j = Continuous sum of elements from 0 to j - Continuous sum of elements from 0 to i => sum(j, i) = sum(0, i) - sum(0, j)
From the above equation, If sum(0, i) = sum(0, j), then sum(i, j) = 0.

So there could be two possibilities for the sub-array with zero sum:

Case 1: Subarray starting from 0 and ending at some index i. sum(0, i) = 0
Case 2: Subarray starting from some index j and ending at some index i. sum(i, j) = 0 where 0 < i < j < n.

Using the above hypothesis, we can solve the problem by traversing the array linearly and storing the sum of all the subarrays starting from the index 0 (Think!). Here is a step by step description :

Let’s use the variable sum to track the current sum from the index 0 to the index i and maxLength to track the max length of the sub-array with zero-sum.
We also use a hash table H to store the sum of the subarrays starting from the index 0 as a key and its end index i as a value i.e. we store it in the form of key-value pair (sum, i).
Now we run a loop from i = 0 to n - 1. Inside the loop:
We calculate the sub-array sum starting from the index 0. If we find the value of the sum equal to zero, then we update the variable maxLength.
```
if (sum == 0)
{
  if (maxLength < i + 1)
      maxLength = i + 1
}
```
Otherwise, if the sum value is already present in the hash table, let’s say sum till index i and sum till index j arethe same, it means that the sum of the subarray X[i + 1 ... j] is 0. In such a scenario, we update the value of the maximum length.
```
else if(H.search(sum) == true)
{
  if(maxLength < i - H[sum])
      maxLength = i - H[sum]
}
```
Otherwise, we store the value of the current index i in the hash table using sum valueas a key i.e. H.insert(sum) = i
By end of the whole loop, we return the value stored in maxLength.

Solution Pseudocode

int largestZeroSubarray(int X[], int n)
{
    HashTable H
    int sum = 0
    int maxLength = 0
    for (int i = 0, i < n; i = i + 1)
    {
        sum = sum + X[i]
        if (sum == 0)
        {
            if (maxLength < i + 1)
                maxLength = i + 1
        }       
        else if(H.search(sum))
        {
            if(maxLength < i - H[sum])
                maxLength = i - H[sum]
        }        
        else
            H.insert(sum) = i
    }
    
    return maxLength
}

Solution Analysis

We are linearly traversing the array and performing one search or one insert operation at each step of the iteration. Time complexity of one insert/search operation = O(1) average. So overall time complexity = n*O(1) = O(n). Space Complexity = O(n), for the hash table

Critical ideas to think!

Can we solve this problem using some other approach?
How do we modify the above approach if we also need to return the indexes of the subarray with zero-sum?
How do we modify the above approach to find the largest subarray with a given sum other than zero?
Can we solve this problem using some other data structures?