largest continious sequence with zero sum.txt

Largest Continuous Sequence Zero Sum
Problem Description

Given an array A of N integers.

Find the largest continuous sequence in a array which sums to zero.



Problem Constraints
1 <= N <= 106

-107 <= A[i] <= 107



Input Format
Single argument which is an integer array A.



Output Format
Return an array denoting the longest continuous sequence with total sum of zero.

NOTE : If there are multiple correct answers, return the sequence which occurs first in the array.



Example Input
A = [1,2,-2,4,-4]


Example Output
[2,-2,4,-4]


Example Explanation
[2,-2,4,-4] is the longest sequence with total sum of zero.


vector<int> Solution::lszero(vector<int> &A) {
    int n=A.size();
    int prefix=0;
    unordered_map<int,int> mp;
    mp.insert({0,-1});
    pair<int,int> index={-1,-1};
    int len=0;
    for(int i=0;i<n;i++){
        
        prefix +=A[i];
        if(mp.find(prefix)!=mp.end()){
            if(len<i-mp[prefix]){
                len=i-mp[prefix];
                index.first=mp[prefix];
                index.second=i;
            }
        }
        else{
          mp.insert({prefix,i});
        }
    }
    if(index.second!=-1){
       vector<int> ans(A.begin()+index.first+1,A.begin()+index.second+1);
       return ans;
    }
    return {};
}