Problem of the day
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 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.
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.
4
1 0 -1 1
3
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.
2
1 1
0
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.
Do we really need to iterate through a subarray each time, to find its sum?
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:
O(N ^ 3), where ‘N’, is the size of ‘Arr’.
We iterate over all subarrays of ‘Arr’ in O(N ^ 2) time (we iterate over ‘i’ in O(N) time and then for each ‘i’ we iterate over ‘j’ in O(N) time, hence the overall time is O(N ^ 2)). Then, for each subarray, we find its sum in O(N) time. Hence the overall time complexity of this solution is O(N * N * N).
O(1)
Since we are not utilizing any extra space the overall space complexity is O(1)