Find if Sum of Subarray = 0 in Kotlin

by

To find if there is any subarray with sum = 0 in an array, we can use a technique called the prefix sum approach. Here’s how it works:

  1. We create a prefix sum array prefixSum that stores the cumulative sum of the elements in the input array array.
  2. We then loop through the prefix sum array, and for each prefix sum value sum, we check if there exists any earlier prefix sum value that is equal to sum or if the current sum value is equal to 0.
  3. If we find such a prefix sum value, it means that the subarray between the two prefix sum values has a sum of 0. We can return true to indicate that a subarray with sum 0 exists.
  4. If we have looped through the entire prefix sum array and haven’t found any subarray with sum 0, we can return false to indicate that no such subarray exists.

Here’s what the code would look like in Kotlin:

Kotlin
fun hasSubarrayWithSumZero(array: IntArray): Boolean {
    // Create a prefix sum array
    val prefixSum = IntArray(array.size)
    prefixSum[0] = array[0]
    for (i in 1 until array.size) {
        prefixSum[i] = prefixSum[i - 1] + array[i]
    }

    // Check if there exists any subarray with sum 0
    val set = HashSet<Int>()
    for (sum in prefixSum) {
        if (sum == 0 || set.contains(sum)) {
            return true
        }
        set.add(sum)
    }

    // No subarray with sum 0 exists
    return false
}
fun main() {
    val array = intArrayOf(3, 4, -7, 3, 1, 3, 1, -4, -2, -2)
    val hasSubarraySumZero = hasSubarrayWithSumZero(array)
    if (hasSubarraySumZero) {
        println("Input array has a subarray with sum 0.")
    } else {
        println("Input array does not have a subarray with sum 0.")
    }
}
  1. We start by creating an empty array prefixSum of the same size as the input array array. This array will store the cumulative sum of the elements in array.
  2. We then initialize the first element of prefixSum to be equal to the first element of array, since the cumulative sum of the first element is simply the value of the first element.
  3. Next, we iterate over the remaining elements of array using a loop that starts from index 1 and ends at index array.size - 1.
  4. Inside the loop, we compute the cumulative sum of the current element of array and all the elements that come before it. We do this by adding the current element to the value of the previous element in prefixSum.
  5. We store the result of the cumulative sum in the current index of prefixSum.
  6. Once the loop has finished executing, we have computed the prefix sum array prefixSum for the input array array.
  7. Next, we iterate over the prefix sum array prefixSum using another loop that starts from index 0 and ends at index prefixSum.size - 1.
  8. Inside the loop, we check if the current element of prefixSum is equal to 0. If it is, it means that there is a subarray in array that has a sum of 0, since the cumulative sum of that subarray would be equal to the current index of prefixSum.
  9. If we find a 0 in prefixSum, we return true from the function, indicating that the input array array has a subarray with sum 0.
  10. If we reach the end of the loop without finding a 0 in prefixSum, it means that there is no subarray in array that has a sum of 0, so we return false from the function.

The time complexity of the hasSubarrayWithSumZero function is O(n), where n is the length of the input array. This is because the function performs two linear scans of the input array and one linear scan of the prefix sum array, each of which takes O(n) time.

The space complexity of the function is O(n), where n is the length of the input array. This is because we create a prefix sum array of size n to store the cumulative sums of the input array elements. Additionally, we use constant space to store the loop index variables and the Boolean result variable, so these do not contribute to the space complexity.

Leave a Comment