New update is available. Click here to update.

Longest Subarray Zero Sum

PROBLEM STATEMENT

Ninja loves playing with numbers. So his friend gives him an array on his birthday. The array consists of positive and negative integers. Now Ninja is interested in finding the length of the longest subarray whose sum is zero.

Input Format:

The first line contains a single integer T, denoting the number of test cases. 

The first line of each test case will contain the integer N, denoting the number of elements in the given array.

The second and last line contains N space-separated integers that denote the value of the elements of the array.

Output Format

The first and only line of each test case in the output contains an integer denoting the length of the longest subarray whose sum is zero.

Note:

You are not required to print the expected output; it has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 10
1 <= N <= 10^4
-10^5 <= arr[i] <= 10^5

Time Limit: 1 sec

Approach 1

We will create the various sub-arrays possible from the given array. We will then eliminate those sub-arrays whose sum is not zero. Out of the remaining sub-arrays, we check the length of each sub-array and see which has the largest length. We will return the largest length as our final answer.

The steps are as follows:

We initialize ‘maxLen’ to store the length of the maximum subset whose sum is zero.
We will iterate over all the elements of the array, i.e., i = 0 to i = N - 1:
- We initialize ‘currSum’ to store the current sum of the sub-array.
- We will iterate over all the elements of the array, i.e., j = i to j = N - 1:
  - We will add arr[j] to ‘curSum’ to store the sum of the present sub-array.
  - If ‘currSum’ is zero, store the maximum of ‘maxLen’ and j - i +1 in ‘maxLen’.
We will return ‘maxLen’ as the final answer.

Try Problem

Approach 2

We can maintain a prefix sum for each index. We can check if standing at a particular index sum is zero. If it is zero, then we store the index value as the length of the sub-array. Then we hold the sum values in a hash map. If the present sum is previously present in the hash map, then it means starting from the previous index till the current index, we get another sub-array whose sum is zero. If the length of this sub-array is greater than the previously stored length, then we modify our answer with this value.

The steps are as follows:

We initialize ‘maxLen’ to store the length of the maximum subset whose sum is zero, ‘sum’ to store the present sum, and hashmap ‘presum’ to keep the previous sums.
We will iterate over all the elements of the array, i.e., i = 0 to i = N - 1:
- We will store the sum of the elements till index i in ‘sum’.
- If ‘sum’ is zero, then we will store i + 1 in maxLen.
- If arr[i] is zero and maxLen is zero, then we will store 1 in maxLen.
- If ‘sum’ is not present in presum, we will store the maximum of ‘maxLen’ and i - presum[sum] in ‘maxLen’.
- We will store i in presum[sum].
We will return ‘maxLen’ as the final answer.

Try Problem