Longest Subarray With Sum Zero

Medium
611.

Longest Subarray With Sum Zero

Longest Subarray With Sum Zero is a medium coding problem on arrays, hash table and prefix sum, asked in Amazon, Samsung and Paytm interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @return {number}
 */
var maxLenZeroSum = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Longest Subarray With Sum Zero — Problem & Solution

Longest Subarray With Sum Zero solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Longest Subarray With Sum Zero is a medium coding problem on arrays, hash table and prefix sum, asked in Amazon, Samsung and Paytm interviews.

  • Difficulty: Medium
  • Topics: Arrays, Hash Table, Prefix Sum
  • Asked at: Amazon, Samsung, Paytm
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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

Hints for Longest Subarray With Sum Zero

  1. Hint 1

    A subarray arr[i+1..j] sums to zero exactly when the prefix sums at i and j are equal.

  2. Hint 2

    So the question becomes: how far apart can two equal prefix sums be?

  3. Hint 3

    Store the first index at which each prefix sum occurs and never overwrite it.

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

Java

public static int maxLenZeroSum(int[] arr) {
    Map<Integer, Integer> first = new HashMap<>();
    int sum = 0, best = 0;
    for (int i = 0; i < arr.length; i++) {
        sum += arr[i];
        if (sum == 0) { best = i + 1; continue; }
        Integer at = first.get(sum);
        if (at == null) first.put(sum, i);
        else if (i - at > best) best = i - at;
    }
    return best;
}

C++

int maxLenZeroSum(vector<int>& arr) {
    unordered_map<int, int> first;
    int sum = 0, best = 0;
    for (int i = 0; i < (int) arr.size(); i++) {
        sum += arr[i];
        if (sum == 0) { best = i + 1; continue; }
        auto it = first.find(sum);
        if (it == first.end()) first[sum] = i;
        else if (i - it->second > best) best = i - it->second;
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets