Largest Subarray with 0 Sum

Largest Subarray with 0 Sum looks like it needs you to test every subarray, but a single sweep with a hash map finds the answer in O(n). The trick is a classic: turn the array into prefix sums and notice when one repeats.

The slow way first

The obvious idea: try every subarray. Pick a start, pick an end, add up the slice, and check if it is zero, keeping the longest one that is. Even if you reuse a running sum for the inner loop, that is two nested loops: O(n²). For a large array it is far too slow.

The question to ask: what do I really need to know at index i? I want to know whether some earlier slice can be peeled off so that what remains sums to zero. Prefix sums turn that into a simple lookup.

The idea: equal prefix sums bracket a zero-sum slice

Let prefix[i] be the sum of nums[0..i]. The sum of the slice from j+1 to i is prefix[i] - prefix[j]. That slice sums to zero exactly when prefix[i] == prefix[j]. So whenever the running prefix sum repeats a value we have seen before, the stretch in between is a zero-sum subarray.

To make it longest, we store the first index where each prefix value appeared, then on a repeat the length is i - first[prefix]. We seed the map with prefix 0 at index -1 so a slice that starts at index 0 is counted correctly.

The key insight: store the first index of each prefix and never overwrite it, so every later repeat measures back to the earliest possible start, giving the widest slice.

Walk through it

Step through the animation. The pointer i scans left to right and prefix accumulates. The map first records the earliest index of each prefix value. Prefix 0 is seeded at index -1, then reappears at index 1 (giving length 1 - (-1) = 2) and again at index 3 — measured back to index -1 that is length 3 - (-1) = 4, the answer.

Pseudocode

first = { 0: -1 }          # maps a prefix sum -> the earliest index it appeared
prefix = 0
best = 0
for each index i with value num in nums:
    prefix = prefix + num
    if prefix is a key in first:
        best = max(best, i - first[prefix])   # zero-sum slice ends here
    else:
        first[prefix] = i                     # remember the FIRST time we saw it
return best

The Python solution

def longest_zero_sum(nums):
    first = {0: -1}
    prefix = 0
    best = 0
    for i, num in enumerate(nums):
        prefix += num
        if prefix in first:
            best = max(best, i - first[prefix])
        else:
            first[prefix] = i
    return best

• first maps a prefix sum → the earliest index at which it occurred. Seeding it with {0: -1} makes a zero-sum prefix (one starting at index 0) measure correctly.
• prefix is the running sum of everything up to and including the current element.
• Lines 7 and 8 are the heart of the trick: a repeated prefix means the slice in between sums to zero, and its length is i - first[prefix].
• We only record a prefix the first time we see it (the else), so every later match spans back to the widest possible start.
• We never need the subarray itself, only its length, so a single best value is enough.

Complexity

We trade O(n) extra space (the map of prefix sums) for the speed win: O(n²) → O(n). The move — accumulate a prefix and watch for a repeat — solves a whole family of subarray-sum questions.

When this pattern shows up

Practice