in he exmple cosdiered in the video,when second zero occurs in prefix sum array and length is 2 why is it not replaces with 0(the location in hashmap?? how come 2 is not better than 0?
Length of longest subaaray wit sum zero
Hello @Vibhuti0206
We are using the hashmap to store the only the first instance of each element in the prefix sum because this will help us find the length of the longest subarray with zero sum.
Consider Test Case
10
0 1 2 -3 4 -4 2 2 3 -6
Prefix sum array for this would be
0 1 3 0 4 0 2 4 7 1
Hashmap (storing only the first instance of each distinct element)
0 - 0
1 - 1
3 - 2
4 - 4
2 - 6
7 - 8
Now how will we go about searching for the longest sub array with sum zero is, we will traverse the array and for each element we will look for the same element but towards the “farthest left”.
Why we look for the same element is because, consider 4 @ index 7 and left farthest 4 is @ index 4, add all the elements from index (4 + 1) to index 7, you will get zero. Hence 7 - 4 = 3 will give us the length of the subarray with sum zero.
Why we look for the same “farthest” left element is because then the difference (above 7 - 4) will be biggest and we will get the length of longest sub array of sum zero.
and Hey !! we have stored all the elements farthest left location (That is location of their of first instance).
That is the reason we need the farthest left and NOT any other location.
2 is NOT better than 0 here !!