Prefix sum problems: Find the largest subarray with sum 0

Problem Statement:

You are given an array with +ve and -ve integers, find the length of the longest subarray with sum 0.

Example:

Input: arr[] = [1, 2, -2, -1, 10, 3]

Output: 4

Explanation: subarray with sum 0 = [1, 2, -2, -1]

Solution 1: Bruteforce Approach

In this approach, we will try all subarrays using 2 nested for loop.

Create a hashmap, to store the prefix sum of each element as key and the index of the element as value.

Traverse the array and add the element to sum.

Check if the sum is already present in the hashmap, if present, then update the max accordingly.

if the sum is not found, then store into the hashmap.

Return the max at the end.

Time Complexity: O(n*n)
Space Complexity: O(1)

Solution 2:

We will use hashmap and prefix sum to solve the problem.

Time Complexity: O(n)
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <unordered_map>
using namespace std;

int solution_1(vector<int> arr)
{
    int n = arr.size();

    int maxLen = 0; 

    for (int i = 0; i < n; i++) 
    {
        int currSum = 0;

        for (int j = i; j < n; j++) 
        {
            currSum += arr[j]; 

            if (currSum == 0)
                maxLen = max(maxLen, j - i + 1);
        }
    }
    return maxLen;
}


int solution_2(vector<int> arr) 
{
    int n = arr.size();
    int prefixSum = 0;
    int maxLen = 0;
    unordered_map<int, int> mpp; 

    mpp[0] = -1;

    for (int i = 0; i < n; i++) 
    {
        prefixSum += arr[i];

        if (mpp.find(prefixSum) != mpp.end()) 
        {

            maxLen = max(maxLen, i-mpp[prefixSum]);
        }
        else 
        {
            
            // Store first occurrence of this prefix sum
            mpp[prefixSum] = i;
        }
    }

    return maxLen;
}


int main()
{
    vector<int> arr =  {1, 2, -2, -1, 10, 3};
  
    cout<<solution_1(arr)<<endl;
    cout<<solution_2(arr)<<endl;

    return 0;
}

Output

4
4