Length of the longest subarray with zero Sum

[Question]: Problem Statement: Given an array containing both positive and negative integers, we have to find the length of the longest subarray with the sum of all elements equal to zero.
Input array = [9, -3, 3, -1, 6, -5]
Result: 5
Explanation: The following subarrays sum to zero:
{-3, 3} , {-1, 6, -5}, {-3, 3, -1, 6, -5}
Since we require the length of the longest subarray, answer is 5

# Approach
// TC: O(N)
// SC: O(N)
func longestArrayWithNSum(arr: [Int]) -> Int {
    
    var mpp: [Int:Int] = [:] // Create an dictionary
    var maxi = 0 // longest Subarray found
    var sum = 0 // sum of elements
    
    for i in 0..<arr.count {
        sum += arr[i]
        if (sum == 0) {
            maxi = i + 1
        } else {
            if mpp[sum] != nil {
                maxi = max(maxi, i - mpp[sum]!)
            } else {
                mpp[sum] = i
            }
        }
    }
    return maxi
}

let inputLongestSubArray = [10, -3, 3, -1, 6, -5]
let outputLongestSubArray = longestArrayWithNSum(arr: inputLongestSubArray)
print("outputLongestSubArray-->", outputLongestSubArray) // 5 which is 10, -3, 3, -1, 6

Leave a Comment

Your email address will not be published. Required fields are marked *