Subarray with given Sum in Kotlin

by

The “Subarray with Given Sum” problem involves finding a subarray within an unsorted array where the sum of its elements is equal to a given target sum. The problem requires returning the left and right indices (1-based indexing) of the subarray.

Here’s a step-by-step explanation of how to solve the problem:

  1. We are given an unsorted array A of size N containing only positive integers and a target sum S.
  2. Initialize two pointers, left and right, both initially pointing to the first element of the array.
  3. Initialize a variable called currentSum to store the sum of the current subarray. Set its initial value to the first element of the array, A[0].
  4. Start iterating through the array using the right pointer until it reaches the end.
  5. In each iteration:
    • Add the value at the right pointer to the currentSum. This represents extending the current subarray by including the current element.
    • Check if currentSum is equal to the target sum S. If it is, we have found a subarray with the desired sum.
      • In this case, add the left and right indices to the result ArrayList (1-based indexing) and return the result.
    • If currentSum is less than the target sum S, move the right pointer to the next element and update currentSum accordingly.
    • If currentSum is greater than the target sum S, move the left pointer to the next element and subtract the value at the left pointer from currentSum. This represents reducing the subarray sum by excluding the element at the left pointer.
    • Repeat steps 5-7 until the right pointer reaches the end of the array.
  6. If no subarray with sum S is found, return an ArrayList containing a single element -1 to indicate that no such subarray exists.

By using the sliding window technique, we maintain a window that slides through the array, adjusting its size based on the comparison of the current sum with the target sum. This approach has a time complexity of O(N) since we only iterate through the array once.

Consider the following array: [1, 2, 3, 7, 5] and the target sum S = 12.

Array: [1, 2, 3, 7, 5]
Indices: 1 2 3 4 5

Current Window: [2, 3, 7]
Current Sum: 12

Finally, the current sum becomes equal to the target sum (12 == 12). We have found a subarray that adds up to the given sum. The left index is 2, and the right index is 4. So, the subarray with the sum 12 is [2, 3, 7].Therefore, the expected output for this example would be 2 4

The Kotlin code for the “Subarray with Given Sum” problem:

Kotlin
fun subarraySum(arr: IntArray, targetSum: Int): Pair<Int, Int> {
    var left = 0
    var right = 0
    var currentSum = arr[0]

    while (right < arr.size) {
        when {
            currentSum == targetSum -> return Pair(left + 1, right + 1)
            currentSum < targetSum -> {
                right++
                if (right < arr.size) {
                    currentSum += arr[right]
                }
            }
            else -> {
                currentSum -= arr[left]
                left++
            }
        }
    }

    return Pair(-1, -1)
}

fun main() {
    val arr = intArrayOf(1, 2, 3, 7, 5)
    val targetSum = 12

    val (left, right) = subarraySum(arr, targetSum)

    if (left == -1 && right == -1) {
        println("No subarray with sum $targetSum found.")
    } else {
        println("Subarray with sum $targetSum found at indices: $left to $right")
    }
}
  1. The subarraySum function takes an array arr of integers and a target sum targetSum as input. It returns a Pair containing the left and right indices of the subarray with the given sum.
  2. The function initializes the left and right variables to 0, representing the starting indices of the subarray window.
  3. The currentSum variable is initialized with the value of the first element in the array, arr[0].
  4. The while loop continues until the right pointer reaches the end of the array.
  5. Inside the loop, there’s a when statement that handles three cases:
    • If currentSum is equal to the targetSum, it means we have found a subarray with the desired sum. In this case, the function returns a Pair containing the left and right indices of the subarray, incremented by 1 to match the 1-based indexing.
    • If currentSum is less than the targetSum, we need to expand the window. The right pointer is incremented, and the value at the new right position is added to the currentSum.
    • If currentSum is greater than the targetSum, we need to shrink the window. The left pointer is incremented, and the value at the left position is subtracted from the currentSum.
  6. If the loop finishes without finding a subarray with the desired sum, the function returns a Pair containing -1 for both the left and right indices, indicating that no such subarray exists.
  7. The main function demonstrates the usage of the subarraySum function. It initializes an example array and target sum.
  8. The subarraySum function is called with the array and target sum, and the returned left and right indices are stored in variables left and right.
  9. If the left and right indices are both -1, it means no subarray with the sum exists, and an appropriate message is printed.
  10. If the left and right indices are not -1, it means a subarray with the sum was found, and a message displaying the indices is printed.

The time complexity of the code is O(N), where N is the length of the input array.

The while loop iterates through the array once, with both the left and right pointers moving at most N steps. Therefore, the time complexity of the code is linear with respect to the size of the input array.

The space complexity of the code is O(1), which means it uses constant space. The space requirements do not depend on the size of the input array. The code only uses a few integer variables to keep track of indices and the current sum, so the space complexity remains constant regardless of the input size.

Leave a Comment