Longest Subarray With Sum Zero — Medium Problem & Solution

Problem statement

Given an array arr that may contain negative numbers, return the length of the longest contiguous subarray whose elements sum to 0.

If no such subarray exists, return 0.

Example 1

Input: arr = [15,-2,2,-8,1,7,10,23]
Output: 5
Explanation: The subarray [-2,2,-8,1,7] sums to 0.

Example 2

Input: arr = [1,2,3]
Output: 0
Explanation: Everything is positive, so no subarray can reach 0.

Example 3

Input: arr = [1,-1,3,-3,4]
Output: 4
Explanation: [1,-1,3,-3] is the longest.

Constraints

• 1 <= arr.length <= 100000
• -1000 <= arr[i] <= 1000

How to solve Longest Subarray With Sum Zero

Let P[j] be the sum of arr[0..j]. Then arr[i+1..j] sums to zero precisely when P[i] == P[j], so the longest zero-sum subarray is the widest gap between two equal prefix sums.

Approach

1. Sweep left to right maintaining the running prefix sum.
2. If the running sum is 0 at index i, the whole prefix works — a candidate of length i + 1.
3. Otherwise, record the first index at which each sum value appears; on a repeat, the candidate length is i - first[sum].
4. Return the largest candidate.

Why it works

Keeping only the first occurrence is what maximises the distance: for a fixed right end j, the leftmost i with P[i] == P[j] gives the longest subarray, and every zero-sum subarray is detected at its own right end.

Complexity

• Time — O(n)
• Space — O(n)

Pitfalls

• Overwriting the stored index on every occurrence yields the shortest such subarray, not the longest.
• Forgetting the sum == 0 case misses subarrays that start at index 0.

Reference solution

Python

from typing import List

def maxLenZeroSum(arr: List[int]) -> int:
    first = {}
    total = 0
    best = 0
    for i, x in enumerate(arr):
        total += x
        if total == 0:
            best = i + 1
        elif total in first:
            best = max(best, i - first[total])
        else:
            first[total] = i
    return best

JavaScript

var maxLenZeroSum = function(arr) {
    var first = {};
    var sum = 0, best = 0;
    for (var i = 0; i < arr.length; i++) {
        sum += arr[i];
        if (sum === 0) { best = i + 1; continue; }
        var key = String(sum);
        if (first[key] === undefined) first[key] = i;
        else if (i - first[key] > best) best = i - first[key];
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Minimum Number of Increments on Subarrays to Form a Target Array Medium
• Find the Winner of an Array Game Medium
• Queries on a Permutation With Key Medium
• Corporate Flight Bookings Medium
• Find the Winner of the Circular Game Medium
• Longest Subsequence With Limited Sum Medium