Find the largest subarray in a array whose sum is zero

Question

Expected Time Complexity : O(N) , where 'N'  is the size of array .

-1000000<=A[i]<=1000000

1<=N<=100000

Example :

-100 -200 300 10000 -5 5

Output : Subarray with zero sums are {-100,-200,300} and {-5,5} . But {-100,-200,300} has the largest size of 3 , henceforth our answer is  3  

Note :

1)Algorithm-explanation is must .

2)Adding code is optional .

3)Use Format option while adding code

Answer 1

LOGIC
maintain a running sum
maintain a map, this map will stores the index of a new sum that we see
if we see a sum again in future, this means that sum of all the elements in between is zero.
Hence by tracking the starting index of "where we first saw this sum" we can estimate the size of array

ALGO

insert '0' in the begning(why ? - this is a sort of edge case, if all elements are zero, then both the ends are inclusive)

start traversing the List from the beginning
    add the element to sum

    if we have seen this sum and our CurrentMaxLen < newLen
        set ans as newLen
    if we have not seen this sum
        set map of newSum = index+1
print ans

CODE BEGINS HERE
int32_t main()

{

    vector<int> tc1 = {5,10,-100,-200,300,-5,5};

    vector<int> tc2 = {0,0,0,0};

    vector<int> tc3 = {0};

    vector<int> tc4 = {1};

    vector<int> a = tc4;

    a.insert(a.begin() , 0);

    unordered_map<int,int> m;

    int ans = 0;

    for(int i=0, sum = 0 ; i<a.size() ; i++)

    {

        sum += a[i];

        if(m[sum])

            ans = max(ans , i-m[sum]+1);

        if(m[sum]==0)

            m[sum] = i+1;

    }

    print(ans);

}

INPUT TC1

5   10   -100   -200   300   -5   5

OUTPUT TC1

5


INPUT TC2

0   0   0   0

OUTPUT TC2

4


INPUT TC3

0

OUTPUT TC3

1


INPUT TC4

1

OUTPUT TC4

0

 

-let me if logic is wrong or any edge cases or if can be improved

Comments

Sorry, question has been modified . You can edit your query and write an answer to the problem instead .