DSA

Largest subarray with 0 sum

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

August 8, 2026

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)

DSAMajority Element IIExtended Boyer-Moore Voting — find all elements appearing more than ⌊n/3⌋ times. Time O(n), Space O(1).DSARemove Duplicates from Sorted Array IIKeep each unique element at most twice in-place. Optimal — Time O(n), Space O(1).DSARotate ArrayCovers: Brute Force, Extra Array, Optimal (Reverse). Optimal — Time O(n), Space O(1).

Brute Force#

Optimal — Prefix Sum + Hash Map#

Related articles