Start learning free

LESSON 212 OF 348 · PARTIAL SUMS #1

Maximum Sum Subarray of Length K in Kotlin: Brute Force, O(n * k)

Practice O(n * k) 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 subarray nums[4...6] is [6, 6, 4], with sum 16, which is the largest of all windows of three. The function returns [4, 6].

    Approach: add up every window

    A window of length k is fixed by its first index. In an array of n elements the first index can be anything from 0 to n - k, so there are n - k + 1 windows. The brute force sums each window from scratch and remembers the best one.

    Here are all six windows of the example:

    startwindowsum
    05, 6, 112
    16, 1, 29
    21, 2, 69
    32, 6, 614
    46, 6, 416
    56, 4, 313

    The largest sum is 16, at start 4, so the answer is [4, 4 + 3 - 1], that is [4, 6].

    Each window costs k additions and there are about n windows, so the total is O(n * k). Neighbouring windows share k - 1 elements, so most of those additions repeat work already done. The next lesson on this problem slides the window instead and brings the time down to O(n).

    Two questions decide the shape of the code: which windows exist, and what to remember about the best one so far. The first answer is the range of start indices, 0 to n - k. The second is a pair of values: the best sum seen, to compare against, and the indices of the window that produced it, since those are what the function must return. Nothing else has to be kept between windows.

    Step by step

    1. Declare maxSum with var, starting at Int.MIN_VALUE. It holds the best window sum so far. The smallest possible Int guarantees that the first window replaces it, even when all the numbers are negative.
    2. Declare answer with var as an empty IntArray, built with intArrayOf(). It will hold the start and end indices of the best window, and is replaced whenever a better one appears.
    3. Loop i over every window start, from 0 to nums.size - k inclusive. The last window of length k begins at that index; any later start would run past the end of the array.
    4. Declare sum inside the loop, starting at 0. Because it lives inside the loop body, every window starts counting from zero.
    5. Loop idx over the window's positions, from i up to but not including i + k. That is exactly k indices.
    6. Add nums[idx] to sum.
    7. Compare after the inner loop. If sum is greater than maxSum, store it in maxSum and set answer to intArrayOf(i, i + k - 1). Using a strict > keeps the earliest window when two windows have the same sum.
    8. Return answer after the outer loop.

    The solution in Kotlin

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

    The Kotlin details worth a closer look:

    • .. includes both ends, until excludes the upper one. The outer loop needs the last start nums.size - k itself, so it uses ... The inner loop needs k indices from i, so i until i + k fits.
    • Precedence in 0..nums.size - k. Arithmetic binds tighter than .., so this means 0..(nums.size - k) and needs no parentheses.
    • Empty ranges. If k is larger than the array, nums.size - k is negative, the range 0..-1 is empty, and the loop never runs. The function then returns the empty array.
    • intArrayOf() and the type. With no arguments it creates an IntArray of length 0. The variable's type is IntArray, so the later assignment of intArrayOf(i, i + k - 1) is accepted.
    • Replacing instead of editing. answer is assigned a brand-new two-element array each time a better window is found, so the array returned at the end is never shared with an earlier result.
    • Int sums can wrap. If the window sum exceeds about 2.1 billion, it silently overflows. Use Long for sums that large.

    Complexity

    Time: O(n * k). There are n - k + 1 windows and each takes k additions. When k is small this is close to linear, and when k is about half of n it is about n² / 4.

    Space: O(1). Besides the two-element result, the function only uses a few integers.

    Edge cases and common mistakes

    • k equals the array length. There is exactly one window, so the function returns [0, nums.size - 1].
    • k is 1. The answer is the position of the largest element, and the earliest one when it repeats.
    • Ties. For [2, 2, 2, 2] with k = 2 every window sums to 4. The strict > keeps the first, so the result is [0, 1]. Using >= would return the last window, [2, 3].
    • All negative numbers. The sentinel Int.MIN_VALUE loses to any real sum, so the best window is still found. Starting maxSum at 0 would never accept a negative window.
    • Off-by-one in the outer range. Writing 0 until nums.size - k would skip the last window. In the example it would never test the window starting at index 5.
    • Returning the sum. The function returns the two indices, not the sum. The sum is only needed internally.
    • k larger than the array. The function returns an empty array. The lesson's inputs don't use such a k.

    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 = [1, 2], k = 3 gives [].
    • nums = [3, 1, 2], k = 3 gives [0, 2], the only window.
    Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free