Similar Problem

Largest subarray of 0's and 1's

Problem Statement

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

Example:

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

Problem Link

Largest Continuous Sequence Zero Sum - InterviewBit

Code

vector<int> Solution::lszero(vector<int> &A) {

    unordered_map<int,int> m; //sum,index where sum ends

    m[0] = -1;

    int n = A.size();
    int sum = 0;
    int maxlen = 0;
    int si,ei;
    for(int i=0;i<n;i++)
    {
        sum+=A[i];//calculating running sum of the array

        if(m.find(sum)!=m.end())//if that sum is already present in the map
        {
            if(maxlen<i-m[sum])
            {
                maxlen = i-m[sum];
                si = m[sum]+1;
                ei = i;
            }
        }
        else
        m[sum] = i;
    }

    vector<int> res;

    if(!maxlen)
    return res;

    for(int i=si;i<=ei;i++)
    res.push_back(A[i]);

    return res;
}