Problem Explanation: Given an array of integers, find the length of the longest subarray with a sum of 0.
Example:
Input: [1, -2, 3, 4, -2, 2, -8, 1, 2, 3]
Output: 8 (the subarray is [-2, 3, 4, -2, 2, -8, 1, 2])
Expected Time Complexity: O(n) Expected Space Complexity: O(n)
Constraints:
- The input array can contain both positive and negative integers.
- The length of the input array is between 1 and 10^6.
Kotlin Solution:
Kotlin
fun largestSubarrayWithZeroSum(arr: IntArray): Int {
val n = arr.size
val map = mutableMapOf<Int, Int>()
var sum = 0
var maxLen = 0
for (i in 0 until n) {
sum += arr[i]
if (arr[i] == 0 && maxLen == 0) {
maxLen = 1
}
if (sum == 0) {
maxLen = i + 1
}
if (map.containsKey(sum)) {
maxLen = maxOf(maxLen, i - map[sum]!!)
} else {
map[sum] = i
}
}
return maxLen
}
fun main() {
val arr = intArrayOf(1, -2, 3, 4, -2, 2, -8, 1, 2, 3)
val maxLength = largestSubarrayWithZeroSum(arr)
println(maxLength) // Output: 5
}