Longest Subarray Zero Sum

Moderate

0/80

Average time to solve is 18m

27 upvotes

Asked in companies

Problem statement

Given an array arr of length N consisting of positive and negative integers, return the length of the longest subarray whose sum is zero.

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

Input Format:

The first line of input contains an integer N, the length of the array.

The second line of input contains N integers, the elements of the array.

Output Format:

The single line contains an integer, the length of the longest subarray whose sum is zero.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

0 <= N <= 10^6    
-10^9 <= arr[i] <= 10^9

Time Limit: 1sec

Sample Input 1:

5
3 -2 1 -2 1

Sample Output 1:

Explanation For Sample Output 1:

There are two subarrays whose sum is zero arr[0...3], arr[2...4] i.e {3, -2, 1, -2}, and {1, -2, 1}

The longest subarray of these is of length 4.

Sample Input 2:

4
1 -1 2 -2

Sample Output 2:

Hint 1

Hint 2

Find the sum for all possible subarrays and return the length of the largest subarray whose sum is zero.

Approaches (2)

Approach 1

Approach 2

Brute Force

The brute force approach will be to calculate the sum for all possible subarrays. To calculate this, for each element(ith, where 0 <= i < N) in the array fix it as the first end of the subarray, initialize the subarray sum with zero, and iterate on the remaining elements(jth, where i <= j < N) of the array, keep adding the current element to the subarray sum and fix it as the second end of the array. If the sum becomes equals to zero then update the largest length.

Time Complexity

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

In the worst case, we will be checking for all possible subarrays. As there will be N^2 number of subarrays possible for a given array of length N. So the time complexity will be of the order of N^2.

Space Complexity

O(1)

In the worst case, only constant extra space is required.

(100% EXP penalty)

Longest Subarray Zero Sum

Console