Zero Sum Subarray

January 19, 2024

Problem #

Given an array of integers nums, find the length of the longest subarray whose sum is zero.

Example:

1. Input: nums = [2, -2, 3, 0, 4, -7] Output: 4 Explanation: The longest zero-sum subarray is [3, 0, 4, -7].

Solution Approach #

The solution involves using a hashmap to store the cumulative sum up to each index. If the same cumulative sum occurs again, it means that the subarray between these indices sums to zero.

Algorithm Steps #

1. Initialize a hashmap to store the cumulative sum and its first occurrence index.
2. Initialize a variable to track the maximum length of a zero-sum subarray.
3. Iterate through the array, updating the cumulative sum.
4. If the cumulative sum is zero or has been seen before, update the maximum length.
5. Otherwise, store the cumulative sum with its index in the hashmap.
6. Return the maximum length.

Code (Python) #

def longestZeroSumSubarray(nums):
    sum_index_map = {0: -1}
    max_length = 0
    cum_sum = 0

    for i, num in enumerate(nums):
        cum_sum += num
        if cum_sum in sum_index_map:
            max_length = max(max_length, i - sum_index_map[cum_sum])
        else:
            sum_index_map[cum_sum] = i

    return max_length

# Test the function
print(longestZeroSumSubarray([2, -2, 3, 0, 4, -7]))  # Output: 4

Time Complexity #

O(n), where n is the number of elements in nums. The array is traversed once.

Space Complexity #

O(n), for the hashmap storing the cumulative sums and their first occurrences.