Problem

Given an integer array that may contain both positive and negative numbers, find the largest contiguous subarray whose sum equals 0. Return the subarray or its indices and the length.

Examples

Example 1

1
2
3

Input: nums = [4, 6, 3, -9, -5, 1, 3, 0, 2]
Output: subarray = [4, 6, 3, -9, -5, 1], length = 6
Explanation: The elements from index 0..5 sum to 0 and form the longest zero-sum subarray.
Similar Problems

Solution

We show two approaches: a brute-force O(n^2) scan and the recommended O(n) prefix-sum + hashmap method that records first occurrence of each prefix sum.

Method 1 — Brute force (enumerate subarrays)

Intuition

Try every possible subarray and compute its sum; track the longest subarray whose sum is 0.

Approach

  1. For each start index i from 0 to n-1:
    • Initialize sum = 0.
    • For each end index j from i to n-1, add nums[j] to sum.
    • If sum == 0, update the best length and store indices.
  2. Return the longest found subarray (or indices).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
 public:
    std::pair<int,int> longestZeroBrute(const std::vector<int>& nums) {
        int n = nums.size();
        int bestLen = 0, bestL = -1, bestR = -1;
        for (int i = 0; i < n; ++i) {
            int s = 0;
            for (int j = i; j < n; ++j) {
                s += nums[j];
                if (s == 0 && j - i + 1 > bestLen) {
                    bestLen = j - i + 1;
                    bestL = i; bestR = j;
                }
            }
        }
        return {bestL, bestR};
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

package main

func longestZeroBrute(nums []int) (int, int) {
        n := len(nums)
        bestL, bestR, bestLen := -1, -1, 0
        for i := 0; i < n; i++ {
                s := 0
                for j := i; j < n; j++ {
                        s += nums[j]
                        if s == 0 && j-i+1 > bestLen {
                                bestLen = j-i+1
                                bestL, bestR = i, j
                        }
                }
        }
        return bestL, bestR
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public int[] longestZeroBrute(int[] nums) {
        int n = nums.length;
        int bestL = -1, bestR = -1, bestLen = 0;
        for (int i = 0; i < n; ++i) {
            int s = 0;
            for (int j = i; j < n; ++j) {
                s += nums[j];
                if (s == 0 && j - i + 1 > bestLen) {
                    bestLen = j - i + 1;
                    bestL = i; bestR = j;
                }
            }
        }
        return new int[]{bestL, bestR};
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

from typing import List, Tuple

class Solution:
        def longest_zero_brute(self, nums: List[int]) -> Tuple[int, int]:
                n = len(nums)
                best_l = -1
                best_r = -1
                best_len = 0
                for i in range(n):
                        s = 0
                        for j in range(i, n):
                                s += nums[j]
                                if s == 0 and (j - i + 1) > best_len:
                                        best_len = j - i + 1
                                        best_l, best_r = i, j
                return best_l, best_r

Complexity

  • ⏰ Time complexity: O(n^2) — two nested loops over indices.
  • 🧺 Space complexity: O(1) — constant extra space.

Method 2 — Prefix-sum + hashmap (recommended)

Intuition

Let pref[i] be the prefix sum of nums[0..i]. If pref[j] == pref[i] with j < i, then the subarray nums[j+1..i] sums to 0. Track the first occurrence index of each prefix sum; when the same sum appears again compute the subarray length and update the best.

Approach

  1. Initialize pref = 0 and a hashmap firstIndex mapping prefix sum -> first index where it appears. Insert firstIndex[0] = -1 to handle subarrays starting at index 0.
  2. Iterate i from 0..n-1: update pref += nums[i].
  3. If pref is in firstIndex, candidate subarray is firstIndex[pref]+1 .. i; update best length if larger. Otherwise store firstIndex[pref] = i.
  4. Return indices of the longest zero-sum subarray.

Edge cases: empty array, all-zeroes array, negative numbers — all handled naturally by prefix sums.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
 public:
    std::pair<int,int> longestZeroHash(const std::vector<int>& nums) {
        std::unordered_map<long long,int> first;
        first[0] = -1;
        long long pref = 0;
        int bestL = -1, bestR = -1, bestLen = 0;
        for (int i = 0; i < (int)nums.size(); ++i) {
            pref += nums[i];
            if (first.find(pref) != first.end()) {
                int len = i - first[pref];
                if (len > bestLen) { bestLen = len; bestL = first[pref] + 1; bestR = i; }
            } else {
                first[pref] = i;
            }
        }
        return {bestL, bestR};
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

package main

func longestZeroHash(nums []int) (int, int) {
        first := map[int]int{0: -1}
        pref := 0
        bestL, bestR, bestLen := -1, -1, 0
        for i, v := range nums {
                pref += v
                if idx, ok := first[pref]; ok {
                        if i-idx > bestLen {
                                bestLen = i-idx
                                bestL, bestR = idx+1, i
                        }
                } else {
                        first[pref] = i
                }
        }
        return bestL, bestR
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    public int[] longestZeroHash(int[] nums) {
        Map<Long, Integer> first = new HashMap<>();
        first.put(0L, -1);
        long pref = 0;
        int bestL = -1, bestR = -1, bestLen = 0;
        for (int i = 0; i < nums.length; ++i) {
            pref += nums[i];
            if (first.containsKey(pref)) {
                int len = i - first.get(pref);
                if (len > bestLen) { bestLen = len; bestL = first.get(pref) + 1; bestR = i; }
            } else {
                first.put(pref, i);
            }
        }
        return new int[]{bestL, bestR};
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

from typing import List, Tuple

class Solution:
        def longest_zero_hash(self, nums: List[int]) -> Tuple[int, int]:
                first = {0: -1}
                pref = 0
                best_l = -1
                best_r = -1
                best_len = 0
                for i, v in enumerate(nums):
                        pref += v
                        if pref in first:
                                length = i - first[pref]
                                if length > best_len:
                                        best_len = length
                                        best_l, best_r = first[pref] + 1, i
                        else:
                                first[pref] = i
                return best_l, best_r

Complexity

  • ⏰ Time complexity: O(n) — single pass with hash map lookups.
  • 🧺 Space complexity: O(n) — the hashmap stores at most one entry per distinct prefix sum.