DSA

Largest subarray with 0 sum

Arrays. Time O(n), Space O(n).

August 8, 2026
PatternPrefix Sum + HashingOptimalO(n) time · O(n) space
Solve on GeeksforGeeks
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²).

cpp
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.

cpp
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)