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
Hint 1
A subarray
arr[i+1..j]sums to zero exactly when the prefix sums atiandjare equal.Hint 2
So the question becomes: how far apart can two equal prefix sums be?
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
- Sweep left to right maintaining the running prefix sum.
- If the running sum is
0at indexi, the whole prefix works — a candidate of lengthi + 1. - Otherwise, record the first index at which each sum value appears; on a repeat, the candidate length is
i - first[sum]. - 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 == 0case 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 bestJava
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