Last Updated: 18 Sep, 2020
Longest Subarray Zero Sum
Moderate
Asked in companies
Given an array arr of length N consisting of positive and negative integers, return the length of the longest subarray whose sum is zero.
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
Approaches
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.
In this approach, we will use a hashmap to store the prefix sums as keys and the value as the lowest index till which the prefix sum occurred. If any prefix sum occurs again in the array(let’s say i is the first index and j is the new index at which the prefix sum occurred again) this means that the sum of elements from (i + 1)th to jth index equals to zero and we will update the largest length.
Note: we will only keep the first index(lowest index) of a prefix sum as we need to find the largest length.