Start learning free

LESSON 213 OF 348 · PARTIAL SUMS #1

Maximum Sum Subarray of Length K in Kotlin: Sliding Window, O(n)

Practice O(n) Read the full explanation

Given an input array of integers and a positive integer k, find out the maximum sum of a contiguous subarray of length exactly k

Example

Input: nums = [5, 6, 1, 2, 6, 6, 4, 3], k = 3
Output: 4 6
Explanation: The subarray nums[4...6] has the maximum sum of 16
STEP 1 OF 8
    Ctrl + Enter to check

    KOTLIN · PARTIAL SUMS #1

    Maximum Sum Subarray Of Length K in Kotlin, explained

    Problem overview

    The function maxSum receives an IntArray called nums and a positive integer k. Among all contiguous subarrays of length exactly k, it must find the one with the largest sum, and return its first and last index as a two-element IntArray.

    In the example, nums = [5, 6, 1, 2, 6, 6, 4, 3] and k = 3. The window [6, 6, 4], at indices 4 to 6, sums to 16, more than any other window of three. The function returns [4, 6].

    Approach: slide the window instead of re-adding it

    The straightforward solution sums every window from scratch: k additions for each of the n - k + 1 windows, which is O(n * k). But two neighbouring windows differ by only two elements. When the window moves one step right, the element at its left edge leaves and a new element enters at its right edge. The new sum is

    new sum = old sum - (element that left) + (element that entered)

    That costs two operations no matter how large k is. The only full sum is the one for the very first window, so the total work is about k + (n - k) steps, which is O(n).

    Take the example. The first window [5, 6, 1] sums to 12. Sliding to start 1, the 5 leaves and the 2 enters: 12 - 5 + 2 = 9, which matches 6 + 1 + 2. Sliding to start 2, the 6 leaves and the 6 enters: 9 - 6 + 6 = 9. Next, 9 - 1 + 6 = 14, then 14 - 2 + 4 = 16, and finally 16 - 6 + 3 = 13. The best sum, 16, belongs to the window that started at index 4.

    Step by step

    1. Start answer as the first window. Declare it with var and give it the bounds 0 and k - 1. If no later window is better, the first one is the result, so an empty starting answer would return nothing in that case.
    2. Declare sum with var, starting at 0. It will always hold the sum of the current window.
    3. Add up the first window. Loop i from 0 to k - 1 and add nums[i] to sum. Using until k stops the loop at index k - 1.
    4. Declare maxSum with var, initialized with sum. The first window is the best seen so far.
    5. Set up a while loop over the remaining starts. Declare var i = 1 and loop while i <= nums.size - k, with i++ as the last line of the body. Window starts 1 to nums.size - k remain.
    6. Slide the window. At the top of the body, subtract nums[i - 1], the element that just left, and add nums[i + k - 1], the element that just entered. The window starting at i covers i to i + k - 1, and the previous one started at i - 1.
    7. Compare. If sum is greater than maxSum, save it and set answer to intArrayOf(i, i + k - 1). The strict > keeps the earliest window on ties.
    8. Return answer after the loop. The increment i++ sits at the bottom of the body, below the comparison, so the steps above run before i advances.

    The solution in Kotlin

    class Solution {
    fun maxSum(nums: IntArray, k: Int): IntArray {
        var answer = intArrayOf(0, k - 1)
        var sum = 0
        for (i in 0 until k) {
            sum += nums[i]
        }
        var maxSum = sum
        var i = 1
        while (i <= nums.size - k) {
            sum = sum - nums[i - 1] + nums[i + k - 1]
            if (sum > maxSum) {
                maxSum = sum
                answer = intArrayOf(i, i + k - 1)
            }
            i++
        }
        return answer
    }
}

    The Kotlin details worth a closer look:

    • Two different is. The loop variable of for (i in 0 until k) exists only inside that loop. After the loop ends, var i = 1 declares a new variable with the same name, which is legal because the first one is out of scope.
    • A while loop for a manual counter. The for loop would also work here, for example for (i in 1..nums.size - k). The lesson uses while so that the start index and the increment are visible. Forgetting i++ would make the loop run forever.
    • Precedence. In nums.size - k, the subtraction happens before the comparison with i, so no parentheses are needed.
    • IntArray creation. intArrayOf(0, k - 1) builds a new two-element array. Each improvement allocates another small array, but only when a better window is found.
    • Int overflow. The running sum is an Int, so totals beyond about 2.1 billion wrap around silently. A Long would avoid that.

    Complexity

    Time: O(n). The first loop runs k times and the while loop runs n - k times. Each pass of the while loop does a constant amount of work. Every element enters the window once and leaves it at most once.

    Space: O(1). Apart from the two-element answer, only a few integers are stored. Compared with the brute force, the time drops from O(n * k) to O(n) at no cost in memory.

    Edge cases and common mistakes

    • k equals the array length. The condition 1 <= nums.size - k is false at once, so the loop doesn't run and the first window [0, k - 1] is returned.
    • Ties. For [2, 2, 2, 2] with k = 2 every window sums to 4. The strict > keeps the earliest, so the function returns [0, 1].
    • All negative numbers. [-5, -1, -9] with k = 1 returns [1, 1]. Because maxSum starts as the first window's sum, rather than 0, a negative sum can still win.
    • Wrong indices when sliding. The element that leaves is nums[i - 1], and the one that enters is nums[i + k - 1]. Using nums[i + k] for the new element reads one position too far, and at the last window it goes past the end of the array.
    • Resetting the sum. Setting sum back to 0 inside the loop would defeat the purpose and lose the previous window's total.
    • k larger than the array. The first loop reads nums[i] beyond the last index and throws an ArrayIndexOutOfBoundsException. The lesson's inputs keep k within the array.

    Testing

    • nums = [5, 6, 1, 2, 6, 6, 4, 3], k = 3 gives [4, 6].
    • nums = [2, 2, 2, 2], k = 2 gives [0, 1].
    • nums = [-5, -1, -9], k = 1 gives [1, 1].
    Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free