Find Length of Largest Subarray with 0 Sum using Hash Map Optimal Solution

Problem Statement❯

Given an array of integers (which may contain both positive and negative numbers), your task is to find the length of the longest contiguous subarray whose elements sum up to 0.

The subarray must consist of consecutive elements.
The array may contain positive numbers, negative numbers, and zeros.
If no such subarray exists, return 0.

Examples❯

Input Array	Output	Description
[1, 2, -3, 3, -1, -2]	6	The entire array sums to 0
[15, -2, 2, -8, 1, 7, 10, 23]	5	Subarray [-2, 2, -8, 1, 7] has sum 0
[1, 2, 3]	0	No subarray has 0 sum
[0, 0, 0, 0]	4	All elements are 0, full array is valid
[4, -1, -3, 1, 2]	5	Entire array has sum 0
[1]	0	Single element not equal to 0
[0]	1	Single 0 is a valid subarray
[]	0	Empty array, no subarrays

Visualization Player

Solution❯

To find the longest subarray with sum 0, we need to understand how the prefix sum (running total) can help us track when a subarray cancels itself out.

We traverse the array from left to right and calculate the sum of elements up to each index—this is called the prefix sum. At any point, if the same prefix sum appears again, it means the subarray between those two indices has a sum of 0.

Let’s understand this with different situations:

Case 1: Prefix sum becomes 0 at index i
This means the subarray from index 0 to i itself has a sum of 0. So we update the maximum length to i + 1.
Case 2: Prefix sum repeats
If the current prefix sum was seen before at index j, it means the elements between index j+1 and the current index cancel out to 0. The length of this subarray is i - j.
Case 3: Prefix sum is seen for the first time
We store it in a map with its index, so that if it repeats later, we can calculate the subarray length.
Case 4: No 0 sum subarray exists
In this case, no prefix sum ever repeats, and the sum is never 0. So the answer remains 0.
Case 5: Entire array has sum 0
This happens when the prefix sum is 0 at the last index. Then the whole array is the longest valid subarray.
Case 6: Array with all zeros
Every prefix sum is 0 here, so we always get subarrays with 0 sum. The longest one is the entire array.

This approach works well because we don’t have to check every possible subarray. Instead, we use a Hash Map to remember where each prefix sum first appeared and use that to quickly calculate lengths of potential zero-sum subarrays. This gives us a very efficient O(n) time solution.

Algorithm Steps❯

Given an array arr of size n.
Initialize an empty Hash Map to store prefix sums and their first occurrence index.
Initialize variables: max_len = 0 and prefix_sum = 0.
Traverse the array:
→ Add the current element to prefix_sum.
→ If prefix_sum == 0, update max_len = current index + 1.
→ If prefix_sum already exists in the map, update max_len as the maximum of current max_len and current index - first occurrence index.
→ Else, store prefix_sum with the current index in the map.
Return max_len.

Code

Python

JavaScript

Java

C++

def max_len_zero_sum_subarray(arr):
    prefix_sum = 0
    max_len = 0
    prefix_map = {}

    for i, num in enumerate(arr):
        prefix_sum += num

        if prefix_sum == 0:
            max_len = i + 1
        elif prefix_sum in prefix_map:
            max_len = max(max_len, i - prefix_map[prefix_sum])
        else:
            prefix_map[prefix_sum] = i

    return max_len

# Sample Input
arr = [15, -2, 2, -8, 1, 7, 10, 23]
print("Length of Largest Subarray with 0 Sum:", max_len_zero_sum_subarray(arr))

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(n)	In the best case, we traverse the array once and find subarrays summing to 0 early, updating the maximum length efficiently.
Average Case	O(n)	The algorithm runs in linear time by computing the prefix sum and checking/recording it in the hash map in constant time for each element.
Worst Case	O(n)	Even in the worst case, we perform a single pass through the array, and all hash map operations (insertion, lookup) are constant time on average.

Space Complexity❯

O(n)

Explanation: In the worst case, all prefix sums may be unique, requiring storage of each sum and its index in the hash map.

⬅ Previous Topic4 Sum Problem

Next Topic ⮕Find Maximum Product Subarray