New update is available. Click here to update.

Solve problems & track your progress

Checkout your overall progress in every topic here

Become

Sensei

in DSA topics

Open the topic and solve more problems associated with it to improve your skills

Check out the skill meter for every topic

See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Problem

Submissions

Longest Subarray With Zero Sum

Contributed by

Shivam Ruhil

Medium

0/80

0 upvotes

Problem Statement

Ninja is given an array ‘Arr’ of size ‘N’. You have to help him find the longest subarray of ‘Arr’, whose sum is 0. You must return the length of the longest subarray whose sum is 0.

For Example:

For N = 5, and Arr = {1, -1, 0, 0, 1}, 
We have the following subarrays with zero sums: 
{{1, -1}, {1, -1, 0}, {1, -1, 0, 0}, {-1, 0, 0, 1}, {0}, {0, 0}, {0}}
Among these subarrays, {1, -1, 0, 0} and {-1, 0, 0, 1} are the longest subarrays with their sum equal to zero. Hence the answer is 4.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains an integer ‘N’, denoting the size of the array ‘Arr’.
The second line contains ‘N’ space-separated integers denoting the elements of ‘Arr’.

Output Format:

You must return an integer representing the length of the longest subarray with a sum equal to zero.

Constraints:

1 <= N <= 10^5
-10^9 <= Arr[i] <= 10^9

The sum of ‘N’ over all test cases is less than or equal to 10^5.
Time Limit: 1 sec.

Sample Input 1:

4
1 0 -1 1

Sample Output 1:

Explanation of Sample Input 1:

The subarrays with sums equal to zero are: {{1, 0, -1}, {0}, {0, -1, 1}, {-1, 1}}.
Among these, {1, 0, -1} and {0, -1, 1} are the longest with length equal to 3.
Hence the answer is 3.

Sample Input 2:

2
1 1

Sample Output 2:

Auto

Console