Largest Subarray with 0 sum

Problem Statement

Given an array of integers, find the maximum length of a subarray whose sum is 0.

Example

Input:
arr = [15, -2, 2, -8, 1, 7, 10, 23]

Output:
5

Explanation:

The longest subarray with sum 0 is:
[-2, 2, -8, 1, 7]

First Approach (Brute Force)

The first idea that comes to mind is:

• Fix a starting index i
• Keep adding elements till index j
• Check if the sum becomes 0
• Track the maximum length

Code (Java – Brute Force)

class Solution {
    int maxLength(int arr[]) {
        int maxLen = 0;

        for (int i = 0; i < arr.length; i++) {
            int sum = 0;
            for (int j = i; j < arr.length; j++) {
                sum += arr[j];

                if (sum == 0) {
                    maxLen = Math.max(maxLen, j - i + 1);
                }
            }
        }
        return maxLen;
    }
}

Problem with this approach

Time Complexity: O(n²)

For large inputs, this may cause TLE (Time Limit Exceeded)

Optimized Approach (Prefix Sum + HashMap)

Main Idea : If the same prefix sum appears again,
then the subarray between those two indices has sum 0.

Why?

prefixSum[j] - prefixSum[i] = 0
prefixSum[j] == prefixSum[i]

• Here prefixSum[j] is the sum of elements from 0 to j and prefixSum[i] is the sum of elements from 0 to i
• If both are same then ,The sum of elements between i+1 and j becomes zero

Why HashMap?

Because we need to:

Store prefix sum

Along with its first occurrence index

Optimized Code (Java – O(n))

class Solution {
    int maxLength(int arr[]) {
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, -1); // to handle subarray starting from index 0

        int sum = 0;
        int maxLen = 0;

        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];

            if (map.containsKey(sum)) {
                maxLen = Math.max(maxLen, i - map.get(sum));
            } else {
                map.put(sum, i);
            }
        }
        return maxLen;
    }
}

Why do we store (0, -1) initially?

This handles the edge case when the subarray starts from index 0.

Example:

arr = [1, -1]
prefix sum at index 1 = 0
length = 1 - (-1) = 2

So -1 represents a virtual index before the array starts.

Complexity Analysis

Time Complexity :O(n)
We traverse the array only once.

Space Complexity : O(n)
Due to HashMap storing prefix sums.

So this is all about this problem
If you found this solution even a bit worst
Please make sure to hit like button and also share it your coding fellows