# Largest subarray with sum equal to 0

This is a typical interview question:

Given an array that contains both positive and negative elements without 0, find the largest subarray whose sum equals 0.

I am not sure if this will satisfy all the edge case. If someone can comment on that, it would be excellent. I also want to extend this to sum equaling to any , not just 0. How should I go about it? And any pointers to optimize this further is also helpful.

from collections import Counter

def sub_array_sum(array,k=0):
start_index = -1
hash_sum = {}
current_sum = 0
keys = set()
best_index_hash = Counter()
for i in array:
start_index += 1
current_sum += i
if current_sum in hash_sum:
hash_sum[current_sum].append(start_index)
else:
if current_sum == 0:
best_index_hash[start_index] = [(0,start_index)]
else:
hash_sum[current_sum] = [start_index]
if keys:
for k_1 in keys:
best_start = hash_sum.get(k_1)
best_end_list = hash_sum.get(k_1)[1:]
for best_end in best_end_list:
if abs(best_start-best_end) in best_index_hash:
best_index_hash[abs(best_start-best_end)].append((best_start+1,best_end))
else:
best_index_hash[abs(best_start-best_end)] = [(best_start+1,best_end)]

if best_index_hash:
(bs,be) = best_index_hash[max(best_index_hash.keys(),key=int)].pop()
print array[bs:be+1]
else:
print "No sub array with sum equal to 0"

def Main():
a = [6,-2,8,5,4,-9,8,-2,1,2]
b = [-8,8]
c = [7,8,-1,1]
d = [2200,300,-6,6,5,-9]
e = [-9,-6,8,6,-14,9,6]
sub_array_sum(a)
sub_array_sum(b)
sub_array_sum(c)
sub_array_sum(d)
sub_array_sum(e)

if __name__ == '__main__':
Main()

• Are only subarrays with contiguous elements from the original array allowed, or arbitrary elements? – Martin R Dec 3 '14 at 9:23
• Yes. Only contiguous elements. – Arman Dec 3 '14 at 9:24
• I think that contiguous subsequences are called substrings. – coderodde Aug 1 '17 at 6:54

I have to admit I didn't fully understood the algorithm. Anyway it seems suboptimal, due to use of heaviweight containers and a nested loops, and is really hard to follow.

I would rather start with an observation that replacing the array with its partial sums reduces the problem to finding two equal elements as distant as possible (two partial sums being equal means the sum in between is 0). This is pretty trivial:

• Calculate partial sums ($O(n)$)

• Stable sort (sum(i),i) tuples ($O(n\log^2n$))

• Scan for largest equal range ($O(n)$)

• Just to explain why this works. You create an array with element like $a'_i = a_0+...+a_i$ So $a'_i = a'_{(i+k)} \Rightarrow a_0+...+a_i = a_0+...+a_i + ... +a_{(i+k)} \Rightarrow 0 = a_{(i+1)} + ... + a_{(i+k)}$ – Fabio F. Dec 3 '14 at 10:35

Here is a linear time solution. The only drawback is that it relies on dictionaries; well, it's still $O(1)$ per dictionary operation, but the constant factors are a little bit larger. Also, I would implement a class for representing exactly solutions to the problem:

class ZeroSubarray:

def __init__(self, arr, from_index, to_index):
self.arr = arr
self.from_index = from_index
self.to_index = to_index

def __str__(self):
ret = ""
ret += "from_index=" + str(self.from_index)
ret += ", to_index=" + str(self.to_index)
ret += ", subarray=["
sep = ""

for i in range(self.from_index, self.to_index):
ret += sep
sep = ", "
ret += str(self.arr[i])

ret += "]"
return ret

def zero_subarray_length(arr):
cumulative_array = [0 for i in range(len(arr) + 1)]

# This is O(n), where n = len(arr):
for i in range(1, len(cumulative_array)):
cumulative_array[i] = cumulative_array[i - 1] + arr[i - 1]

map = {}

# This is O(n) as well
for index in range(len(cumulative_array)):
current_value = cumulative_array[index]

if current_value not in map.keys():
list = [index]
map[current_value] = list
else:
map[current_value].append(index)

best_distance = 0
best_start_index = -1

# O(n) too. Each index into cumulative is stored in a dicttionary
# and so the size of the dict is O(n):
for value, list in map.items():
min_index = list
max_index = list[-1]
current_distance = max_index - min_index
if best_distance < current_distance:
best_distance = current_distance
best_start_index = min_index

return ZeroSubarray(arr, best_start_index, best_start_index + best_distance)

print(zero_subarray_length([2, 3, 6, -1, -4]))


Hope that helps.