Start learning free

LESSON 291 OF 348 · SLIDING WINDOW

Subarray of Given Sum in Kotlin: O(n) Sliding Window, O(1) Space

Practice O(n) Read the full explanation

Given an array of non-negative integers and a number target, find a continous subarray whose sum is equal to target.

Return the start and end indices denoting this subarray.

If there are multiple solutions, you can return any of them.


Example:

Input: nums = [1, 1, 5, 2, 1, 3, 10, 2, 1], k = 21
Output: [2, 6]
Explanation: 5 + 2 + 1 + 3 + 10 = 21

Note:

1. The input array contains only non-negative integers.

2. Your algorithm should run in O(n) time and use O(1) extra space.


STEP 1 OF 8
    Ctrl + Enter to check

    KOTLIN · SLIDING WINDOW

    Subarray Of Given Sum Ii in Kotlin, explained

    Problem overview

    You get an IntArray of non-negative numbers and a target. Find a continuous subarray whose elements add up to target and return its first and last index as a two-element IntArray. If several subarrays work, any one is accepted.

    For [1, 1, 5, 2, 1, 3, 10, 2, 1] with a target of 21, the answer is [2, 6], because 5 + 2 + 1 + 3 + 10 = 21. The lesson asks for O(n) time and O(1) extra space.

    The solution returns [-1, -1] when no subarray adds up to the target.

    Approach

    The brute force tries every pair of ends and adds up the elements between them, which is O(n^3), or O(n^2) if you keep running sums. Both are too slow for the required O(n).

    The key fact is that all numbers are non-negative. Adding an element to a subarray never lowers its sum, and removing one never raises it. That gives a simple rule for a window [j...i]:

    • if the sum is too big, the only fix is to shrink the window from the left;
    • if the sum is too small, extend the window to the right.

    The right end i moves once through the array, and the left end j only moves to the right. Neither goes back, so the work is linear. The only extra storage is the two indices and the running sum, so the space is constant. This is what makes the window better than a hash map of prefix sums, which would need O(n) space.

    If the array could hold negative numbers, the rule would break: removing an element could make the sum bigger, and the window couldn't decide which way to move.

    Step by step

    1. Two edges and a total. j and sum start at 0. They are vars because the loop updates them. The window is [j...i] and sum is always the total of its elements.
    2. Loop over the right end. The for loop over nums.indices makes each element in turn the new right end.
    3. Add the new element. sum += nums[i] keeps sum in step with the window.
    4. Shrink while too big. The inner while loop runs while j < i and sum > target. The check j < i keeps at least nums[i] in the window. A single element that is larger than the target stays in the window, and the sum stays too big until the next element arrives and j passes over it.
    5. Drop the left element. Inside the loop, nums[j] is subtracted from sum and then j is incremented. The order matters: subtract first, while j still points to the element being dropped.
    6. Check for a match. After the inner loop, if sum == target the window is a solution, so return intArrayOf(j, i) right away.
    7. Nothing found. After the for loop, return intArrayOf(-1, -1).

    The solution in Kotlin

    class Solution {
    fun subarraySum(nums: IntArray, target: Int): IntArray {
        var j = 0
        var sum = 0
        for (i in nums.indices) {
            sum += nums[i]
            while (j < i && sum > target) {
                sum -= nums[j]
                j++
            }
            if (sum == target) {
                return intArrayOf(j, i)
            }
        }
        return intArrayOf(-1, -1)
    }
}

    Kotlin details worth knowing:

    • intArrayOf(j, i) builds an IntArray, the primitive int[] of the JVM. A List or Pair would not match the declared return type.
    • for (i in nums.indices) gives you the index directly, which you need here because the answer is made of indices, not values.
    • sum is an Int, a 32-bit number whose overflow wraps silently. The lesson's inputs are small, but a very large array of large values could overflow it; a Long would be the safe type in that case.

    Following the example

    With nums = [1, 1, 5, 2, 1, 3, 10, 2, 1] and a target of 21, the window grows while the sum stays at or below 21. After i = 5 the sum is 1 + 1 + 5 + 2 + 1 + 3 = 13. Adding 10 at i = 6 makes it 23, which is more than 21. The inner loop subtracts nums[0] (sum 22, j = 1) and then nums[1] (sum 21, j = 2). Now sum == target, so the function returns [2, 6].

    Complexity

    Time: O(n). The outer loop runs n times. The inner loop moves j forward by one on each pass, and j never goes back, so across the whole run it runs at most n times in total.

    Space: O(1). Only j, i and sum are stored, plus the two-element result.

    Edge cases and common mistakes

    • No match. For [1, 2, 3] with a target of 7 the function returns [-1, -1].
    • Zeros. Zeros are non-negative, so they are allowed. For [0, 0, 4] with a target of 0 the function returns [0, 0]: the first zero alone is already a valid subarray.
    • A single element. If one element equals the target, the window is that element alone and the result has j == i.
    • Dropping the j < i check. Without it, the window could become empty, and j could run past i.
    • Returning values instead of indices. The answer is the positions of the first and last elements, not the elements.
    • Using if instead of while to shrink. A big new element can require dropping several old ones, so one step is not enough.

    Testing

    • [1, 1, 5, 2, 1, 3, 10, 2, 1], target 21: [2, 6].
    • [1, 2, 3], target 7: [-1, -1].
    • [0, 0, 4], target 0: [0, 0].
    Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free