[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