Explorer
Data Structures & Algorithms

Find the maximum length of a subarray whose sum is 0.

Problem Statement

Given an array `arr` of integers, find the length of the longest sub-array with sum equal to `0`.

Examples

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

Output: 5

Explanation: The largest subarray with sum 0 is [-2, 2, -8, 1, 7] whose length is 5.

Input: arr = [2, 10, 4]

Output: 0

Explanation: Combining the input according to Largest Subarray with Sum 0 logic yields 0.

Complexity

Time Complexity: O(N)

Space Complexity: O(N)

Hints

šŸ’” Hint 1: If cumulative sum at index i equals cumulative sum at index j, the subarray between j+1 and i sums to 0. šŸ’” Hint 2: Store the first occurrence index of each prefix sum in a hash map. šŸ’” Hint 3: If currentSum is 0, subarray from 0 to i sums to 0 (length = i + 1).

Editorial & Approach

Problem Overview & Intuition

A subarray [j + 1 ... i] has sum 0 if and only if prefixSum[i] === prefixSum[j]. Storing the earliest occurrence of each prefix sum in a map allows maximizing i - j in linear O(N) time.

Step-by-Step Approach

  1. Initialize map = new Map(), maxLen = 0, currentSum = 0.
  2. Iterate i from 0 to arr.length - 1.
  3. Accumulate currentSum += arr[i].
  4. If currentSum === 0, maxLen = i + 1.
  5. If map.has(currentSum), update maxLen = Math.max(maxLen, i - map.get(currentSum)).
  6. Else, store map.set(currentSum, i).
  7. Return maxLen.

Optimal Implementation (JavaScript)

function maxLenSubarrayZeroSum(arr) {
  const map = new Map();
  let maxLen = 0, currentSum = 0;
  for (let i = 0; i < arr.length; i++) {
    currentSum += arr[i];
    if (currentSum === 0) maxLen = i + 1;
    if (map.has(currentSum)) maxLen = Math.max(maxLen, i - map.get(currentSum));
    else map.set(currentSum, i);
  }
  return maxLen;
}

Complexity Analysis

Time Complexity O(N) ā€” single traversal with O(1) average hash map lookups.
Space Complexity O(N) ā€” prefix sum map.

Edge Cases & Corner Traps Handled

  • No subarray sums to 0: returns 0.
  • Entire array sums to 0: returns arr.length.
  • Single element array [0]: returns 1.

Largest Subarray with Sum 0

Hard
Given an array `arr` of integers, find the length of the longest sub-array with sum equal to `0`.
Example Scenarios
1Example 1
Input: arr = [15, -2, 2, -8, 1, 7, 10, 23]
Output: 5
Explanation:

The largest subarray with sum 0 is [-2, 2, -8, 1, 7] whose length is 5.

2Example 2
Input: arr = [2, 10, 4]
Output: 0
Explanation:

Combining the input according to Largest Subarray with Sum 0 logic yields 0.

Editor
Loading Editor...
arr =
[15, -2, 2, -8, 1, 7, 10, 23]
Output:Click "Run" above to execute and verify your code here.
5