Largest Subarray With a Sum of 0

Given an array of integers, return the length of the longest contiguous subarray whose sum is 0, or 0 if there is none.

Example

Input:  [15, -2, 0, -8, 3, 7, 10, 23]
Output: 5   (-2, 0, -8, 3, 7)

Input:  [1, 2, 3]
Output: 0

Find a Subarray With a Sum of 0 only asks whether such a subarray exists. Here the longest one is needed.

Brute force: every start, with a running sum

public class Main {
    static int longestZeroSum(int[] nums) {
        int best = 0;
        for (int start = 0; start < nums.length; start++) {
            long sum = 0;
            for (int end = start; end < nums.length; end++) {
                sum += nums[end];
                if (sum == 0) {
                    best = Math.max(best, end - start + 1);
                }
            }
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(longestZeroSum(new int[]{15, -2, 0, -8, 3, 7, 10, 23}) + " " + longestZeroSum(new int[]{1, 2, 3}));
    }
}

5 0

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

Optimal: first index of each prefix sum

Let prefix[i] be the sum of the first i elements. The subarray nums[i..j] (indices i up to but not including j) sums to 0 exactly when prefix[i] == prefix[j]. For the longest such subarray ending at j, pair j with the earliest i that had the same prefix sum.

So store each prefix sum's first index in a HashMap, and never overwrite it. The empty prefix (sum 0 at index 0) is stored before the loop, so subarrays that start at the beginning are found too.

prefix[6] = 15 was first seen at index 1, so nums[1..6] sums to 0 and has length 5.

import java.util.HashMap;
import java.util.Map;

public class Main {
    static int longestZeroSum(int[] nums) {
        Map<Long, Integer> firstSeen = new HashMap<>();
        firstSeen.put(0L, 0);
        long prefix = 0;
        int best = 0;
        for (int j = 0; j < nums.length; j++) {
            prefix += nums[j];
            Integer i = firstSeen.get(prefix);
            if (i != null) {
                best = Math.max(best, j + 1 - i);
            } else {
                firstSeen.put(prefix, j + 1);
            }
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(longestZeroSum(new int[]{15, -2, 0, -8, 3, 7, 10, 23}) + " " + longestZeroSum(new int[]{1, 2, 3}));
        System.out.println(longestZeroSum(new int[]{1, -1, 3, -3}) + " " + longestZeroSum(new int[]{0, 0, 0}));
    }
}

5 0
4 3

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

The map stores prefix positions (j + 1 after reading nums[j]), so j + 1 - i is the length of the subarray from index i through index j. get returns null for a missing key, so the value is read into an Integer and compared with null. The map's key type is Long, and prefix is a long, so both are boxed to Long. An int key would be boxed to Integer, which never equals a Long.

Edge cases

• Whole array sums to 0: found through the stored (0, 0) entry.
• Zeros: a single 0 is a zero-sum subarray of length 1.
• Overflow: prefix sums are kept in long, so a sum of int values does not wrap.
• Longest subarray with sum k: the same code with firstSeen.get(prefix - k).