Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Longest Subarray with Zero Sum

MEDIUMProblemSolveExternal Links

Description

Given an array arr[] containing both positive and negative integers, find the length of the longest subarray whose elements sum to zero.

A subarray is a contiguous part of the array, formed by picking one or more consecutive elements while keeping their original order. Among all subarrays that have a sum equal to zero, you must return the length of the longest one. If no such subarray exists, return 0.

Examples

Example 1

Input: arr = [15, -2, 2, -8, 1, 7, 10, 23]

Output: 5

Explanation: The subarray [-2, 2, -8, 1, 7] (indices 1 through 5) has a sum of (-2) + 2 + (-8) + 1 + 7 = 0, and its length is 5. No longer zero-sum subarray exists in this array.

Example 2

Input: arr = [1, 0, -4, 3, 1, 0]

Output: 5

Explanation: The subarray [0, -4, 3, 1, 0] (indices 1 through 5) sums to 0 + (-4) + 3 + 1 + 0 = 0, giving a length of 5. This is the longest zero-sum subarray.

Example 3

Input: arr = [2, 10, 4]

Output: 0

Explanation: No subarray of this array sums to zero. Every possible contiguous segment has a strictly positive sum, so the answer is 0.

Constraints

  • 1 ≤ arr.length ≤ 10^6
  • -10^3 ≤ arr[i] ≤ 10^3

Editorial

Brute Force

Intuition

The simplest way to solve this problem is to consider every possible subarray and check whether its sum equals zero.

Imagine you are given a row of cards, each showing a positive or negative number. To find the longest stretch of cards that totals zero, you could pick a starting card, then keep adding cards to the right one by one, running a tally of the total. Every time that running tally hits zero, you have found a zero-sum subarray, and you record its length if it is the longest you have seen.

You repeat this for every possible starting card. By the end, you will have checked every contiguous stretch in the array, guaranteeing you have not missed any zero-sum subarray.

Step-by-Step Explanation

Let's trace through arr = [1, -1, 3, -3, 2] to see the brute force in action:

Step 1: Initialize maxLen = 0. We will try every starting index.

Step 2: Start with i = 0. Set currSum = 0.

  • Add arr[0] = 1 → currSum = 1. Not zero.
  • Add arr[1] = -1 → currSum = 0. Zero-sum subarray of length 2 found! Update maxLen = 2.
  • Add arr[2] = 3 → currSum = 3. Not zero.
  • Add arr[3] = -3 → currSum = 0. Zero-sum subarray of length 4 found! Update maxLen = 4.
  • Add arr[4] = 2 → currSum = 2. Not zero.

Step 3: Move to i = 1. Set currSum = 0.

  • Add arr[1] = -1 → currSum = -1. Not zero.
  • Add arr[2] = 3 → currSum = 2. Not zero.
  • Add arr[3] = -3 → currSum = -1. Not zero.
  • Add arr[4] = 2 → currSum = 1. Not zero.

Step 4: Move to i = 2. Set currSum = 0.

  • Add arr[2] = 3 → currSum = 3. Not zero.
  • Add arr[3] = -3 → currSum = 0. Zero-sum subarray of length 2! maxLen stays 4.
  • Add arr[4] = 2 → currSum = 2. Not zero.

Step 5: Move to i = 3. Set currSum = 0.

  • Add arr[3] = -3 → currSum = -3. Not zero.
  • Add arr[4] = 2 → currSum = -1. Not zero.

Step 6: Move to i = 4. Set currSum = 0.

  • Add arr[4] = 2 → currSum = 2. Not zero.

Result: maxLen = 4. The longest zero-sum subarray is [1, -1, 3, -3].

Brute Force — Trying All Subarrays — Watch how we fix each starting index i, then extend j rightward accumulating a running sum. Whenever the sum hits zero, we have found a zero-sum subarray.

Algorithm

  1. Initialize maxLen = 0
  2. For each starting index i from 0 to n-1:
    • Set currSum = 0
    • For each ending index j from i to n-1:
      • Add arr[j] to currSum
      • If currSum equals 0, update maxLen = max(maxLen, j - i + 1)
  3. Return maxLen

Code

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int maxLen(vector<int>& arr) {
        int n = arr.size();
        int maxLen = 0;

        for (int i = 0; i < n; i++) {
            int currSum = 0;
            for (int j = i; j < n; j++) {
                currSum += arr[j];
                if (currSum == 0) {
                    maxLen = max(maxLen, j - i + 1);
                }
            }
        }

        return maxLen;
    }
};
class Solution:
    def maxLen(self, arr: list[int]) -> int:
        n = len(arr)
        max_len = 0

        for i in range(n):
            curr_sum = 0
            for j in range(i, n):
                curr_sum += arr[j]
                if curr_sum == 0:
                    max_len = max(max_len, j - i + 1)

        return max_len
class Solution {
    public int maxLen(int[] arr) {
        int n = arr.length;
        int maxLen = 0;

        for (int i = 0; i < n; i++) {
            int currSum = 0;
            for (int j = i; j < n; j++) {
                currSum += arr[j];
                if (currSum == 0) {
                    maxLen = Math.max(maxLen, j - i + 1);
                }
            }
        }

        return maxLen;
    }
}

Complexity Analysis

Time Complexity: O(n²)

The outer loop runs n times and the inner loop runs up to n times for each starting index. The total number of subarray checks is n*(n+1)/2, which simplifies to O(n²). Each check involves a constant-time addition and comparison.

Space Complexity: O(1)

We only use a handful of variables (maxLen, currSum, i, j) regardless of input size. No additional data structures are allocated.

Why This Approach Is Not Efficient

The brute force examines all O(n²) subarrays. When n can be as large as 10^6, this results in roughly 5 × 10^11 operations — far too many to complete within typical time limits (which usually allow about 10^8 operations per second).

The core issue is redundant computation: when we move from starting index i to i+1, we throw away all the prefix sum information we accumulated. We recompute sums from scratch for each starting position.

Key insight: If the prefix sum at index i equals the prefix sum at index j (where j > i), then the subarray from index i+1 to j must have a sum of zero. This is because the prefix sum grew by zero in that range — everything added between those two points cancelled out. By storing prefix sums in a hash map, we can detect repeated prefix sums in O(1) time, reducing the overall complexity from O(n²) to O(n).

Optimal Approach - Prefix Sum with Hash Map

Intuition

Think of walking along a trail where your elevation changes with each step — some steps take you up (positive numbers) and others bring you down (negative numbers). Your running elevation from the start is the prefix sum.

Now, if you find yourself at the same elevation at two different points on the trail, it means that between those two points, you went up and down by equal amounts — the net change is zero. The stretch between those two same-elevation points is a zero-sum subarray.

To find the longest such stretch, we store the first time we reach each elevation (prefix sum) in a hash map. If we encounter the same elevation again later, the distance between the first occurrence and the current position gives the length of a zero-sum subarray. By only storing the first occurrence, we guarantee we always get the longest possible subarray for that prefix sum value.

There is one subtle detail: we must also handle the case where the prefix sum itself is zero (meaning the subarray from the start to the current index sums to zero). We do this by pre-inserting the value 0 at index -1 into the hash map, representing the "elevation before the first step."

Step-by-Step Explanation

Let's trace through arr = [15, -2, 2, -8, 1, 7, 10, 23]:

Step 1: Initialize prefixSum = 0, maxLen = 0, and a hash map firstSeen = {0: -1}.
The entry {0: -1} means "prefix sum 0 was first seen before index 0," handling subarrays starting from the beginning.

Step 2: Process arr[0] = 15.

  • prefixSum = 0 + 15 = 15
  • Is 15 in firstSeen? No.
  • Store {15: 0} in firstSeen.
  • firstSeen = {0: -1, 15: 0}

Step 3: Process arr[1] = -2.

  • prefixSum = 15 + (-2) = 13
  • Is 13 in firstSeen? No.
  • Store {13: 1}.
  • firstSeen = {0: -1, 15: 0, 13: 1}

Step 4: Process arr[2] = 2.

  • prefixSum = 13 + 2 = 15
  • Is 15 in firstSeen? YES, at index 0.
  • Length = 2 - 0 = 2. Update maxLen = max(0, 2) = 2.
  • Do NOT update firstSeen[15] (keep first occurrence for longest subarray).

Step 5: Process arr[3] = -8.

  • prefixSum = 15 + (-8) = 7
  • Is 7 in firstSeen? No.
  • Store {7: 3}.

Step 6: Process arr[4] = 1.

  • prefixSum = 7 + 1 = 8
  • Is 8 in firstSeen? No.
  • Store {8: 4}.

Step 7: Process arr[5] = 7.

  • prefixSum = 8 + 7 = 15
  • Is 15 in firstSeen? YES, at index 0.
  • Length = 5 - 0 = 5. Update maxLen = max(2, 5) = 5.

Step 8: Process arr[6] = 10.

  • prefixSum = 15 + 10 = 25
  • Is 25 in firstSeen? No. Store {25: 6}.

Step 9: Process arr[7] = 23.

  • prefixSum = 25 + 23 = 48
  • Is 48 in firstSeen? No. Store {48: 7}.

Result: maxLen = 5. The subarray from index 1 to 5, which is [-2, 2, -8, 1, 7], sums to zero.

Prefix Sum + Hash Map — Detecting Repeated Prefix Sums — Watch how we maintain a running prefix sum and store the first index where each sum is seen. When a prefix sum repeats, the subarray between the two occurrences has sum zero.

Algorithm

  1. Initialize prefixSum = 0, maxLen = 0
  2. Create a hash map firstSeen and insert {0: -1} (handles subarrays starting from index 0)
  3. For each index i from 0 to n-1:
    • Add arr[i] to prefixSum
    • If prefixSum already exists in firstSeen:
      • Compute length = i - firstSeen[prefixSum]
      • Update maxLen = max(maxLen, length)
    • Else:
      • Store firstSeen[prefixSum] = i (record the first occurrence only)
  4. Return maxLen

Code

#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

class Solution {
public:
    int maxLen(vector<int>& arr) {
        int n = arr.size();
        unordered_map<int, int> firstSeen;
        int prefixSum = 0;
        int maxLen = 0;

        // Seed: prefix sum 0 at virtual index -1
        firstSeen[0] = -1;

        for (int i = 0; i < n; i++) {
            prefixSum += arr[i];

            if (firstSeen.find(prefixSum) != firstSeen.end()) {
                int length = i - firstSeen[prefixSum];
                maxLen = max(maxLen, length);
            } else {
                firstSeen[prefixSum] = i;
            }
        }

        return maxLen;
    }
};
class Solution:
    def maxLen(self, arr: list[int]) -> int:
        n = len(arr)
        first_seen = {0: -1}  # seed: prefix sum 0 at index -1
        prefix_sum = 0
        max_len = 0

        for i in range(n):
            prefix_sum += arr[i]

            if prefix_sum in first_seen:
                length = i - first_seen[prefix_sum]
                max_len = max(max_len, length)
            else:
                first_seen[prefix_sum] = i

        return max_len
import java.util.HashMap;

class Solution {
    public int maxLen(int[] arr) {
        int n = arr.length;
        HashMap<Integer, Integer> firstSeen = new HashMap<>();
        int prefixSum = 0;
        int maxLen = 0;

        // Seed: prefix sum 0 at virtual index -1
        firstSeen.put(0, -1);

        for (int i = 0; i < n; i++) {
            prefixSum += arr[i];

            if (firstSeen.containsKey(prefixSum)) {
                int length = i - firstSeen.get(prefixSum);
                maxLen = Math.max(maxLen, length);
            } else {
                firstSeen.put(prefixSum, i);
            }
        }

        return maxLen;
    }
}

Complexity Analysis

Time Complexity: O(n)

We traverse the array exactly once. At each step, we perform one hash map lookup and at most one insertion, both of which are O(1) on average. Therefore the total time is O(n).

Space Complexity: O(n)

In the worst case, every prefix sum is unique, so the hash map stores n+1 entries (including the seed entry for 0). This gives O(n) additional space.