Largest Subarray with 0 Sum

Photo by Caleb Woods on Unsplash

Given an array having both positive and negative integers. The task is to compute the length of the largest subarray with a sum of 0.

Examples:

Input: arr[] = {15,-2,2,-8,1,7,10,23}, n = 8
Output: 5
Explanation: The largest subarray with sum 0 is -2 2 -8 1 7.

Input: arr[] = {2,10,4}, n = 3
Output: 0
Explanation: There is no subarray with 0 sum.

Input: arr[] = {1, 0, -4, 3, 1, 0}, n = 6
Output: 5
Explanation: The subarray is 0 -4 3 1 0.

Constraints:
1 <= n <= 10^5
-1000 <= arr[i] <= 1000, for each valid i

Approach

Let us build a generic solution instead of only figuring out for subarray with sum = 0.

The most basic approach will be to scan through all the present subarrays and store them as the current answer if any subarrays get the sum = target. We update our answer, if we get a better length. But this approach will be time-consuming as we need to scan through the array twice in 2 loops, thus increasing the time complexity to O(n ^ 2).

Better Approach

A better approach will be to make use of the prefix sum.