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 ?
Advertisement
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.