Largest Subarray with Sum 0, thesarfo

Length of the longest subarray summing to zero. [15,-2,2,-8,1,7,10,23] → 5 ([-2,2,-8,1,7]).

Brute force: every subarray’s sum, tracking the longest zero-sum one — O(n³).

Optimal — prefix sum + hashmap: if the same prefix sum reappears at two indices, the elements between them sum to zero. Store each prefix sum’s first occurrence index; on a repeat, the gap is a candidate answer.

public static int maxLen(int[] arr) {
    HashMap<Integer, Integer> prefixSumMap = new HashMap<>();
    int maxLength = 0;
    int sum = 0;

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

        if (sum == 0) {
            maxLength = i + 1;
        }

        if (prefixSumMap.containsKey(sum)) {
            maxLength = Math.max(maxLength, i - prefixSumMap.get(sum));
        } else {
            prefixSumMap.put(sum, i);
        }
    }

    return maxLength;
}

Time: O(n). Space: O(n).