Topics › Arrays › Hard

Largest Subarray with Sum 0

Medium TUF ID 605 A2Z

Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given an integer array nums, possibly containing zeros and negative numbers. Return the length of the longest contiguous subarray whose elements sum to 0. If no such subarray exists, return 0.

Constraints: 0 ≤ n ≤ 10^5, values fit in a 32-bit signed integer (so sums may not).

Example 1

nums = [15, -2, 2, -8, 1, 7, 10, 23]
answer = 5

The subarray [-2, 2, -8, 1, 7] sums to zero and nothing longer does.

Example 2

nums = [1, 2, 3]
answer = 0

All prefix sums are strictly increasing, so no non-empty subarray sums to zero.

Example 3

nums = [0, 0, 0]
answer = 3

A zero on its own is a valid zero-sum subarray, and the whole array sums to zero too.

Approach 1: Brute force

Intuition. Try every starting index i, extend the subarray one element at a time to the right, and keep a running sum. Whenever the running sum hits zero, the subarray nums[i .. j] qualifies and its length is j - i + 1. The running sum avoids the third loop a truly naive solution would use to re-add the elements of each subarray.

Algorithm.

1. For each i, set sum = 0.
2. For each j ≥ i, add nums[j] to sum. If sum == 0, update best = max(best, j - i + 1).
3. Return best.

static int bruteForce(int[] nums) {
    int n = nums.length, best = 0;
    for (int i = 0; i < n; i++) {
        long sum = 0;
        for (int j = i; j < n; j++) {
            sum += nums[j];
            if (sum == 0) best = Math.max(best, j - i + 1);
        }
    }
    return best;
}

Complexity. Time O(n^2): every pair (i, j) is visited once. Space O(1).

The sum is a long. Adding up to 10^5 values of size 2 × 10^9 can reach 2 × 10^14, and more to the point, a wrapped int sum can equal zero when the true sum is 2^32. The Java file tests [2000000000, 2000000000, 294967296], whose true sum is exactly 2^32: an int implementation reports length 3, the correct answer is 0.

For n = 10^5 the quadratic approach does 5 × 10^9 additions, which is too slow.

Approach 2: Optimal, prefix sums and a hash map

Intuition. Let P[j] be the sum of nums[0 .. j], with P[-1] = 0 for the empty prefix. The sum of nums[i+1 .. j] is P[j] - P[i]. So a subarray sums to zero exactly when two prefix sums are equal: P[j] == P[i] means nums[i+1 .. j] is a zero-sum subarray of length j - i.

To make j - i as large as possible for a given j, we want the earliest i with the same prefix value. A hash map from prefix value to the first index where it occurred answers that in constant time. Walk left to right, maintain the running prefix, and either report a match (i - firstSeen) or record the prefix if it is new. Never overwrite an existing entry: a later index would only shorten future answers.

Seeding the map with 0 → -1 handles subarrays that start at index 0: if P[j] == 0 then nums[0 .. j] itself sums to zero, length j - (-1) = j + 1.

Algorithm.

1. firstSeen = {0 → -1}, prefix = 0, best = 0.
2. For each index i: prefix += nums[i].
   • If prefix is in the map at index first, best = max(best, i - first).
   • Otherwise store prefix → i.
3. Return best.

static int optimal(int[] nums) {
    Map<Long, Integer> firstSeen = new HashMap<>();
    firstSeen.put(0L, -1);                           // the empty prefix has sum 0 and ends at index -1
    long prefix = 0;
    int best = 0;
    for (int i = 0; i < nums.length; i++) {
        prefix += nums[i];
        Integer first = firstSeen.get(prefix);
        if (first != null) best = Math.max(best, i - first);   // nums[first+1 .. i] sums to zero
        else firstSeen.put(prefix, i);                         // keep only the earliest index
    }
    return best;
}

Dry run on nums = [15, -2, 2, -8, 1, 7, 10, 23]:

Prefix 15 first appeared at index 0 and reappears at index 5, so nums[1 .. 5] has length 5.

Complexity. Time O(n): one pass with O(1) average map operations. Space O(n) for the map in the worst case (all prefixes distinct).

Why is keeping the earliest index enough? For a fixed j, the candidate lengths are j - i over all i with P[i] == P[j]; the smallest such i gives the largest length, and it is also the one we met first, so the first insertion is the only one we ever need.

Edge cases and pitfalls

• Empty array. Returns 0; the loop body never runs.
• Zeros. A single 0 is a zero-sum subarray of length 1. Both approaches handle it because the prefix repeats immediately (P[i-1] == P[i]).
• Whole array sums to zero. Needs the seed 0 → -1; without it [-1, 1, -1, 1] would report 2 instead of 4.
• Overwriting the map entry. Using put unconditionally stores the latest index and silently shrinks answers. Only insert when the key is absent.
• Overflow. Use long for the running prefix and as the map key. The [2000000000, 2000000000, 294967296] test demonstrates a false zero under int arithmetic.
• Negative numbers. Essential to the problem and harmless to the algorithm; prefix sums simply go up and down.

Related problems

• Two Sum introduced the “look up the complement in a hash map” pattern this solution reuses on prefix sums.
• Longest subarray with sum K is the same technique with prefix - K as the lookup key.
• Count subarrays with given sum stores counts instead of first indices.
• Count subarrays with given xor K swaps addition for xor.