DSA
Largest subarray with 0 sum
Arrays. Time O(n), Space O(n).
Key insighttry it first, then reveal
Maintain a running prefix sum. If the same prefix sum appears at indices j and i (with j < i), then the subarray [j+1..i] has sum zero.
Practice Link
Given an array arr containing both positive and negative integers, the task is to compute the length of the largest subarray that has a sum of 0.
Brute Force#
Try every subarray [i..j] by accumulating a running sum. When the sum becomes 0, update the maximum length. Simple but O(n²).
class Solution {
public:
int maxLen(vector<int>& arr) {
int n = arr.size();
int maxLen=0;
for(int i=0;i<n;i++)
{
int sum = 0;
for(int j=i;j<n;j++)
{
sum += arr[j];
if(sum==0)
maxLen = max(maxLen, j-i+1);
}
}
return maxLen;
}
};
Time Complexity: O(n^2)
Space Complexity: O(1)
Optimal — Prefix Sum + Hash Map#
Maintain a running prefix sum. If the same prefix sum appears at indices j and i (with j < i), then the subarray [j+1..i] has sum zero. Store the first occurrence of each prefix sum in a map. If the prefix sum reaches 0 itself, the subarray from index 0 to i is valid. A single pass achieves O(n) time with O(n) hash-map space.
class Solution {
public:
int maxLen(vector<int>& arr) {
unordered_map<int,int> mp;
int sum = 0, maxLen=0;
for(int i=0;i<arr.size();i++)
{
sum += arr[i];
if(sum==0)
maxLen = i+1;
else{
if(mp.find(sum) != mp.end())
maxLen = max(maxLen, i - mp[sum]);
else
mp[sum] = i;
}
}
return maxLen;
}
};
Time Complexity: O(n)
Space Complexity: O(n)