Largest Subarray With 0 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 integers, write a program to find the length of longest subarray with sum equal to 0. In general, for all j > i, find max (j - i + 1) among all subarray with zero-sum. Note: Length of subarray starting from index i and ending at index j will be 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

Brute force approach using three nested loops
Solution approach using two nested loops
Efficient approach using hash table

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 maximum length of subarray with zero-sum.

We initialise variable maxLength to track maximum length of the subarray with zero-sum.
Now we run two nested loops to generate all pair of indices (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.
For every pair (i, j), we run another loop from k = i to j to calculate 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 (maxLength < j - i + 1), maxLength = j - i + 1. Here length of each subarray is j - i + 1.
After nested loops, we return value stored in variable maxLength.

Solution pseudocode

largestSubarrayZeroSum(X, n)
    maxLength = 0
    // Consider every possible subarray [i, j]
    for i from 0 to n - 1
        for j from i to n - 1
            subArraySum = 0
            // Calculate the sum of the current subarray
            for k from i to j
                subArraySum = subArraySum + X[k]
            // Update the maximum length if the sum is zero
            if subArraySum == 0
                maxLength = max(maxLength, j - i + 1)

    return maxLength

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 of above three nested loops: analysis of loop in programming.

We are using constant extra space. Space complexity = O(1).

Optimised solution using two nested loops

Solution idea

Now critical questions are: Can we further optimise the time complexity? Can we avoid the innermost loop from k = i to j to calculate subarray sum? One idea is: If we know sub-array sum from i to j, we can easily calculate the sub-array sum from i to j + 1 in O(1). Subarray sum (i, j+1) = Subarray sum (i, j) + X[j + 1].

Here we run outer loop from i = 0 to n - 1 to pick the starting index i, and run inner loop from j = i to n - 1 to calculate the running sum of all sub-arrays starting from index i. Inside inner loop, if subarray sum is equal to zero, we calculate its length and update max subarray length found so far. This is an optimised version of the above approach, where we are running only two nested loops.

Solution pseudocode

largestSubarrayZeroSum(X, n)
    maxLength = 0
    // Consider each index as the subarray's starting point
    for i from 0 to n - 1
        subArraySum = 0
        // Extend the subarray one element at a time
        for j from i to n - 1
            subArraySum = subArraySum + X[j]
            if subArraySum == 0
                maxLength = max(maxLength, j - i + 1)

    return maxLength

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 = Total number of nested loops iteration * O(1) = O(n^2) * O(1).

We are using constant extra space. So space complexity = O(1).

Solution approach 3: An efficient idea using hash table

Solution idea

Now critical questions are: Can we improve the time complexity to O(n)? Can we solve this problem using a single loop? Let’s think! Suppose sum(j, i) is the sub-array sum from index j to i, where j < i.

Here we can identify one critical property related to sum(j, i): The continuous sum of elements from j to i = Continuous sum of elements from 0 to i - Continuous sum of elements from 0 to j - 1 => sum(j, i) = sum(0, i) - sum(0, j - 1). If sum(0, i) = sum(0, j - 1), then sum(j, i) = 0.

Suppose prefixSum[i] is the sum of the array elements from index 0 through i. So a subarray has sum zero in either of these situations:

Case 1 (The subarray starts at index 0): If prefixSum[i] == 0, then the sum from index 0 to i is zero, i.e. sum(0, i) = prefixSum[i] = 0.
Case 2 (The subarray starts after index 0): Suppose the prefix sums at two indices j and i are equal, where j < i. The sum added between them must be zero: prefixSum[i] - prefixSum[j] = 0. So the subarray from j + 1 to i has sum zero.

For example, with X = [3, -1, -2, 5, -2], the prefix sums are [3, 2, 0, 5, 3].

prefixSum[2] == 0, so the subarray [3, -1, -2] (indices 0 through 2) sums to zero.
prefixSum[0] == prefixSum[4] == 3, so the subarray [-1, -2, 5, -2] (indices 1 through 4) also sums to zero.

Using the above hypothesis, we can solve the problem by traversing the array linearly and storing the sum of all subarrays starting from index 0 (prefix sum) in the hash table. Here are the steps:

Solution steps

We initialise variables prefixSum (to track the subarray sum starting from index 0 to i) and maxLength (to track the max length of sub-array with zero-sum) with 0.
We use hash table H to store the sum of subarrays starting from index 0 as key and end index i as value. In other words, we store it in the form of key-value pair (prefixSum, i).
Now we run loop from i = 0 to n - 1. Inside the loop:
We calculate sub-array sum starting from index 0 (prefixSum).
If prefixSum is equal to zero, we have found case 1 of the above possibilities. So we update variable maxLength i.e. if (maxLength < i + 1), maxLength = i + 1.
```
prefixSum = prefixSum + X[i]
// The subarray from index 0 to i has a zero sum
if prefixSum == 0
  maxLength = max(maxLength, i + 1)
```
Otherwise, there can be chance of case 2. So we search prefixSum in the hash table.
If prefixSum is not present in hash table, we store current index i in the hash table using prefixSum as a key i.e. H.insert(prefixSum) = i.
Otherwise, If prefixSum is present in hash table, it means we have already stored some previous index H[prefixSum] in the hash table with the same value of prefixSum. This is a case 2 where subarray sum from index 0 to i is equal to subarray sum from index 0 to H[prefixSum]. In other words, we can say that the sum of subarray from index H[prefixSum] + 1 to i is equal to 0. So we update the value of maximum length i.e. if(maxLength < i - H[prefixSum]), maxLength = i - H[prefixSum].
```
else if H does not contain prefixSum
  // Store the first index where this prefix sum appears
  H[prefixSum] = i
else
  // A repeated prefix sum indicates a zero-sum subarray
  maxLength = max(maxLength, i - H[prefixSum])
```
By end of the whole loop, we return the value stored in maxLength.

Solution pseudocode

largestZeroSubarraySum(X)
    firstIndex = empty hash map
    prefixSum = 0
    maxLength = 0

    for i from 0 to length(X) - 1
        prefixSum = prefixSum + X[i]
        if prefixSum == 0
            // The subarray from index 0 through i has a zero sum
            maxLength = max(maxLength, i + 1)
        else if firstIndex does not contain prefixSum
            // Store the first index where this prefix sum appears
            firstIndex[prefixSum] = i
        else
            // A repeated prefix sum indicates a zero-sum subarray
            maxLength = max(maxLength, i - firstIndex[prefixSum])

    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 a different approach?
How should we modify the above approach if we also need to return all indexes of the subarray with zero-sum?
What adjustments should be made to the above approach to find the largest subarray with a given sum other than zero?
Is it possible to solve this problem using some other data structures?

Length of Largest Subarray with Zero Sum

Let’s understand the problem!

Discussed solution approaches

Brute force idea using three nested loops

Solution idea and steps

Solution pseudocode

Solution analysis

Optimised solution using two nested loops

Solution idea

Solution pseudocode

Solution analysis

Solution approach 3: An efficient idea using hash table

Solution idea

Solution steps

Solution pseudocode

Solution analysis

Critical ideas to think!

Suggested coding problems to solve

More from EnjoyAlgorithms

Self-paced Courses and Blogs