Find the length of largest subarray with 0 sum

Given an array of integers, find the length of the longest sub-array with sum equals to 0.

Examples :

Input: arr[] = {15, -2, 2, -8, 1, 7, 10, 23};
Output: 5
Explanation: The longest sub-array with 
elements summing up-to 0 is {-2, 2, -8, 1, 7}

Input: arr[] = {1, 2, 3}
Output: 0
Explanation:There is no subarray with 0 sum

Here is an approach to this problem

The Efficient approach

hash_map = {} 
  
    max_len = 0
  
    curr_sum = 0
  
    for i in range(len(arr)): 
        curr_sum += arr[i] 
  
        if arr[i] is 0 and max_len is 0: 
            max_len = 1
  
        if curr_sum is 0: 
            max_len = i + 1
        if curr_sum in hash_map: 
            max_len = max(max_len, i - hash_map[curr_sum] ) 
        else: 
  
            # else put this sum in dictionary 
            hash_map[curr_sum] = i 
  
    return max_len 

But fails for test cases like ,

[8, -8, 7, -7, 15, -15] OR
[10, -10, 12, -12, 13, -13]

Do you have another approach to this problem ?

Answer

To spell out the solution from the comment. First create a generator to yield all sub-arrays:

def gen_subarrays(arr):
    for i in range(len(arr)):
        for j in range(i+1, len(arr)+1):
            yield arr[i:j]

then a function to yield all arrays with a zero sum:

def find_zero_sums(sarrays):
    for sa in sarrays:
        if sum(sa) == 0:
            yield sa

and then a function to keep track of the longest one:

def longest_zero_sum(arr):
    longest = []
    for zs in find_zero_sums(gen_subarrays(arr)):
        if len(zs) > len(longest):
            longest = zs
    return longest

output of:

print(longest_zero_sum([15, -2, 2, -8, 1, 7, 10, 23]))
print(longest_zero_sum([1,2,3]))
print(longest_zero_sum([8, -8, 7, -7, 15, -15]))
print(longest_zero_sum([10, -10, 12, -12, 13, -13]))
print(longest_zero_sum([1,3,0,4,5]))

is

[-2, 2, -8, 1, 7]
[]
[8, -8, 7, -7, 15, -15]
[10, -10, 12, -12, 13, -13]
[0]

You can get a more efficient solution if you sort the subarray indices on descending lengths. Then the first subarray you find that sums to zero is the longest one:

def gen_subarrays(arr):
    indices = [(i,j) for i in range(len(arr)) for j in range(i+1, len(arr)+1)]
    indices.sort(key=lambda (i,j): i-j)  # sort on length (-(j-i))
    for i, j in indices:
        yield arr[i:j]

def longest_zero_sum(arr):
    for sa in gen_subarrays(arr):
        if sum(sa) == 0:
            return sa
    return []

the output is the same as above.