Find the length of largest subarray with 0 sum

Difficulty: Hard

Asked in: Microsoft

Understanding the Problem

Problem Description: Given an array A[] of n integer elements, find the length of the longest subarray with sum equals to 0.

For Example:

Input : A[] = {15, -2, 0, -8, 3, 7, 10, 23}

Output : 5

Explanation : The largest subarray with 0 sum is -2, 0, -8, 3, 7

Possible follow-up questions to ask the interviewer:-

Is it allowed to modify the array? ( Ans: Sure, but a subarray is an ordered contiguous segment of the original array)
What if no subarray has a sum equal to 0? ( Ans: Just return 0)

Solutions

We are discussing two ways to solve this problem :

Brute Force Approach I : Using 3 nested loops.
Brute Force Approach II : Using 2 nested loops.
Using Hash Table: Fill Hash Table with sum up to all positions from 0 and check if two elements in the Hash Table have the same value or value equal to 0.

1. Brute force approach I : Using 3 nested loops

A simple solution is to check for all subarrays one by one and see if its sum is equal to zero or not. For this, we generate all ( i, j): i <= j pairs and calculate the sum between.

Pseudo-Code

int maxLengthSubarraySumToZero(int A[], int n)
{
    int maxLen = 0
    for(i = 0 to n-1)
    {
       for(j = i to n-1) 
       {  
            int sum = 0
            for(k = i to j)
                sum = sum + A[k]
            if(sum == 0)
            {
              if(maxLen < j-i+1)
                maxLen = j-i+1
            }
       }
    }
    return maxLen
}

Complexity Analysis

Time Complexity: O(n³) (Why?)

Space Complexity: O(1)

Critical ideas to think!

In the above approach, the sum of the subarray is calculated in o(n). Could you optimize it using some pre-computation?

2. Brute force approach II : Using 2 nested loops

This is the optimized version of the above approach. The idea is to start at all positions in the array and calculate running sums. The outer loop picks the beginning element, the inner loop finds the possible sum from the first element picked by the outer loop and if sum comes out to be zero, it checks the length and updates it with max length.

Pseudo-Code

int maxLengthSubarraySumToZero(int A[], int n)
{
    int maxLen = 0
    for (i = 0 to n-1)
    {
        int sum = 0
        for (j = i to n-1)
        {
            sum = sum + A[i]
            if(sum == 0)
            {
                maxLen = max(maxLen, j-i+1)
            }
        }
    }
    return maxLen
}

Complexity Analysis

Time Complexity: O(n²) (Why?)

Space Complexity: O(1)

Critical ideas to think!

How many subarrays are possible for an array?

3. Hash Table

The idea is to store the sum of all the subarrays starting from the beginning. From that, if any of the values repeat itself, let’s say sum till i index and sum till j index is same, it means that the sum of elements in the subarray A[i+1…..j] is 0. Moreover, if the sum any index i is 0, then the subarray A[0…i] has sum of its elements equal to 0.

Solution Steps

Create a hash table H and store sum and its ending index as key-value pairs.
Declare a variable maxLen = 0, which will store the maximum length of subarray whose sum is zero.
Iterate through the array and for every A[i], calculate the sum from 0 to i.
If sum turns out to be 0, then update maxLen to i, if (maxLen < i).
Check if that sum is present in the hash table or not.

If exist, then update the maxLen if ( i - H[sum]> maxLen ) to i - H[sum].
If not, insert it in hashmap, H[sum] = i.

5. Return maxLen.

Pseudo-Code

int maxLengthSubarraySumToZero(int A[], int n)
{
    Create a HashTable H
    int sum = 0
    int maxLen = 0
    for(i = 0 to n-1)
    {
        sum = sum + A[i]
        if (sum == 0)
        {
            if (maxLen < i)
            {
                maxLen = i+1
            }
        }
        else if(sum in H)
        {
            if(maxLen < i-H[sum])
            {
                maxLen = i-H[sum]
            }
        }
        else
            H[sum] = i
    }
    return maxLen
}