Find the largest continuous sequence in a array which sums to zero.(https://www.interviewbit.com/problems/largest-continuous-sequence-zero-sum/)

largestContiguousSequenceZeroSum_intervieBit.cpp

/*
Largest Continuous Sequence Zero Sum :
(https://www.interviewbit.com/problems/largest-continuous-sequence-zero-sum/)
Find the largest continuous sequence in a array which sums to zero.

Example:
Input:  {1 ,2 ,-2 ,4 ,-4}
Output: {2 ,-2 ,4 ,-4}

Input: arr[] = {15, -2, 2, -8, 1, 7, 10, 23};
Output:{-2, 2, -8, 1, 7}

Input: arr[] = {1, 2, 3}
Output: {}
There is no subarray with 0 sum

Input: arr[] = {1, 0, 3}
Output: {0}
*/


/*
A simple solution is to consider all subarrays one by one and check the sum of every subarray. 
We can run two loops: the outer loop picks a starting point i and the inner loop tries all subarrays starting from i. 
Time complexity of this method is O(n^2).
*/

vector<int> lszero(vector<int> &A) {
    vector<int> ans ;
    int curr_start = -1 , curr_end = -1 , global_start = -1 , global_end = -1 ;
    
    for(int i = 0 ; i < A.size() ; i++)
    {
        curr_start = -1 , curr_end = -1 ;
        int sum = 0 ;
        for(int j = i ; j <A.size() ; j++)
        {
            sum += A[j] ;
            if(sum == 0)
            {
                curr_start = i ;
                curr_end = j+1 ;
                
                if(global_end - global_start < curr_end - curr_start)
                {
                    global_start = curr_start ;
                    global_end = curr_end ;
                }
            }
        }
    }
    
    if(global_start != -1 && global_end != -1)
    {
        for(int i = global_start ; i < global_end ; i++)
        {
            ans.push_back(A[i]) ;
        }
        return ans ;
    }
    
    return ans ;
}

/*
More efficient approach - O(n) time and O(n) space ::

Lets try to reduce the problem to a much simpler problem. 
Lets say we have another array sum where

  sum[i] = Sum of all elements from A[0] to A[i]
Note that in this array, sum of elements from A[i] to A[j] = Sum[j] - Sum[i-1]

We need to find j and i such that sum of elements from A[i] to A[j] = 0
 Or Sum[j] - Sum[i-1] = 0
 Or Sum[j] = Sum[i-1]
Now, the problem reduces to finding 2 indices i and j such that sum[i-1] = sum[j] .


There are total 3 cases that needs to be taken care of ::

case 1 : If no maximum zero-sum subarray has been identified yet and there’s a 0 element, 
the maximum zero-sum array is trivially composed of the 0 number itself

case 2 : If the running sum reaches zero from the beginning of the array, 
the longest zero-sum subarray consists of the entire array till the index we reached

case 3 : If a previous intermediate sum is found, it means that between the previous sum XX and 
the current sum XX there must have been an interval of values which sum to zero. 
Check for the maximum between the current maximum length and the length of this intermediate interval

*/

vector<int> lszero(vector<int> &A) {
    vector<int> ans ;
    
    if(A.size() == 0)
        return ans ;
    
    int start = -1 , end = -1 ;  
    unordered_map<int , int> Hash ;
    int sum = 0 ;
    for(int i = 0 ; i < A.size() ; i++)
    {
        sum += A[i] ;
        
		//case 1
        if(A[i] == 0 && end - start == 0)
        {
            start = i ;
            end = i+1 ;
        }
		
		//case 2
        if(sum == 0)
        {
            start = 0 ;
            end = i+1 ;
        }
        
		//case 3
        if(Hash.find(sum) == Hash.end())
        {
            Hash[sum] = i ;
        }
        else
        {
            int j = Hash[sum] ;
            if(end - start < i - j)
            {
                end = i+1 ;
                start = j+1 ;
            }
        }
    }
    
    if(start != -1 && end != -1)
    {
        for(int i = start ; i < end ; i++)
        {
            ans.push_back(A[i]) ;
        }
        return ans ;
    }
    
    return ans ;
}