Last Updated: 3 Nov, 2022
Longest Subarray With Zero Sum
Moderate
Asked in company
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.
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.
Approaches
Approach:
We can iterate over all subarrays of ‘Arr’ and calculate their sum by traversing through the subarray. If the sum of the subarray is found to be zero then we consider the length of the current subarray as a candidate for the maximum length. Finally, we return the length of the longest subarray with zero-sum.
Algorithm:
- Ans = 0
- for ‘i’ from 0 to ‘N - 1’:
- for ‘j’ from ‘i’ to ‘N - 1’:
- Sum = 0
- for ‘k’ from ‘i’ to ‘j’:
- Sum += Arr[k]
- if(Sum == 0)
- Ans = max(Ans, j - i + 1)
- for ‘j’ from ‘i’ to ‘N - 1’:
- return Ans
Approach:
We create the prefix sum array of ‘Arr’. We iterate over all subarrays of ‘Arr’, similar to the brute force approach, but instead of traversing the subarray to find its sum, we use the precalculated prefix sums array to find the sum of the current subarray.
Algorithm:
- Create an array called ‘PrefixSum’ of size ‘N’.
- PrefixSum[0] = Arr[0]
- Ans = (Arr[0] == 0)
- for ‘i’ from 1 to ‘N - 1’:
- PrefixSum[i] = PrefixSum[i - 1] + Arr[i]
- if(PrefixSum[i] == 0)
- Ans = max(Ans, i + 1)
- for ‘i’ from 1 to ‘N - 1’:
- for ‘j’ from ‘i’ to ‘N - 1’:
- if(PrefixSum[j] == PrefixSum[i - 1])
- Ans = max(Ans, j - i + 1)
- if(PrefixSum[j] == PrefixSum[i - 1])
- for ‘j’ from ‘i’ to ‘N - 1’:
- return Ans
Approach:
We make the following two observations:
- Inspired by the previous prefix sums approach, we can observe that for any two indices ‘i’ and ‘j’ such that i < j, we can say that if ‘PrefixSum[i]’ is equal to ‘PrefixSum[j]’, then the subarray from ‘i + 1’ to ‘j’, has its sum equal to zero.
- For any index ‘j’, it is always beneficial to find the smallest ‘i’ such that ‘PrefixSum[i]’ is equal to ‘PrerfixSum[j]’ if we want to find the longest subarray with zero-sum ending at ‘j’.
Hence, we use a HashMap to store the first occurrence of an element in ‘PrefixSum’. Then, we iterate over all indices of ‘Arr’ and if the current ‘PrefixSum’ has occurred before, then we take the smallest index at which it occurs to find the longest subarray with zero-sum and ending at the current index. Likewise, we find the length of the longest array with zero-sum.
Algorithm:
- PrefixSum = 0
- Ans = 0
- Create an empty HashMap called ‘FirstIndex’.
- FirstIndex[0] = -1
- for ‘i’ from 0 to ‘N - 1’:
- PrefixSum += Arr[i]
- if(‘PrefixSum’ is present in ‘FirstIndex’)
- Ans = max(Ans, i - FirstIndex[PrefixSum])
- else
- FirstIndex[PrefixSum] = i;
- return Ans