# Longest Continous Zero Sum Subarray

• Find the length of longest continuous subarray within an array (containing at least one number) whose sum equals zero.

For example, given the array [1,0,-1,2],

The longest continuous subarray of zero-sum is [1,0,-1] , which has length = 3.

Python prototype:

``````class Solution(object):
def longestContinousZeroSumSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""``````

• One solution I have is first accumulate the nums array, then it will help us quickly know the sum between any indices, it's a very useful technique.

Once we have the accumulated nums array, we just need to try all the combination of ranges and see if we can find the sum equals to 0 and if the range is longest.

Here is an example code in Java:

``````public int longestContinousZeroSumSubArray(int[] nums) {
int n = nums.length, max = 0;

// accumulate the nums
for (int i = 1; i < n; i++) {
nums[i] += nums[i - 1];
}

for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
// calculate the sum between i ... j
int sum = nums[j] - (i > 0 ? nums[i - 1] : 0);

if (sum == 0 && j - i + 1 > max) {
max = j - i + 1;
}
}
}

return max;
}
``````

• Nice code with time complexity of O(n ^ 2), Could you optimize the time complexity of your algorithm further? :-)

• Aha, we can optimize to O(n), after we have the accumulated nums array, we just need to go through this array and find if there's 0 or two identical numbers, if we found them, update the max length. :)

• This is the optimized O(n) solution:

``````public int longestContinousZeroSumSubArray(int[] nums) {
int n = nums.length, max = 0;

// accumulate the nums
for (int i = 1; i < n; i++) {
nums[i] += nums[i - 1];
}

Map<Integer, Integer> map = new HashMap<>();

for (int i = 0; i < nums.length; i++) {
int num = nums[i];

if (num == 0)
max = Math.max(max, i + 1);
else if (map.containsKey(num))
max = Math.max(max, i - map.get(num));
else
map.put(num, i);
}

return max;
}
``````

• good job, it's O(n) now :D

• @vaid-abhi : You can keep a track of start and end index while updating max, your end index will be `i` and start will be something like `max-i`