Longest Subarray Zero Sum

Easy
0/40
Average time to solve is 15m
168 upvotes
Asked in companies
AmazonAdobeDelhivery

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2 
5
1 3 -1 4 -4
4
1 -1 2 -2 
Sample Output 1:
2
4 
Explanation for Sample Output 1:
In the first test case, the given array is (1, 3, -1, 4, -4). The sub-arrays we can create are (1), (3), (-1), (4), (-4), (1, 3), (3, -1), (-1, 4), (4, -4), (1, 3, -1), (3, -1, 4), (-1, 4, -4), (1, 3, -1, 4), (3, -1, 4, -4), (1, 3, -1, 4, -4). Out of them only (4, -4) is the sub array whose sum is zero.Length of this sub array is 2 and hence we return 2 as the final answer.

In the second test case, the given array is (1, -1, 2, -2). The sub-arrays we can create are (1), (-1), (2), (-2), (1, -1), (-1, 2), (2, -2), (1, -1, 2), (-1, 2, -2), (1, -1, 2, -2). Out of them sub arrays with zer sum are (1, -1), (2, -2), (1, -1, 2, -2). Out of them only (1, -1, 2, -2) has the longest length of 4. Hence we return 4 as the final answer.
Sample Input 2:
2 
3
4 -5 1
4
1 2 1 -2
Sample Output 2 :
3
0
Hint

 Can you create the different sub-arrays?

Approaches (2)
Brute Force

   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.
Time Complexity

O(N^2), where N is the number of elements of the array.

 

As we keep an element fixed and checked for all values from1 to ‘N’, there are at most ‘N^2’ iterations. Hence the overall complexity is O(N^2).

Space Complexity

O(1), no extra space required.

 

As we are not using any extra space. Hence, the overall space complexity is O(1).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Longest Subarray Zero Sum
Full screen
Console