Start learning free

LESSON 235 OF 414 · PARTIAL SUMS #1

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

Practice O(n * k) Read the full explanation

Given an input array of integers and a positive integer k, find the contiguous subarray of length exactly k with the maximum sum, and return its first and last indices.

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

    SCALA · PARTIAL SUMS #1

    Maximum Sum Subarray Of Length K in Scala, explained

    Problem overview

    The method maxSum receives an Array[Int] called nums and a positive integer k. It looks at every continuous subarray of length exactly k, finds the one with the largest sum, and returns its first and last indices as a two-element array.

    For nums = [5, 6, 1, 2, 6, 6, 4, 3] and k = 3, the window at indices 4 to 6 holds 6, 6, 4 and sums to 16, which beats every other window. The method returns [4, 6].

    Approach: add up every window

    There are only n - k + 1 windows of length k in an array of n elements, one for each possible start index. The brute force is direct: for each start, add up its k elements, compare the sum with the best so far, and remember the indices if it is better.

    Each window costs k additions, and there are about n windows, so the total is O(n * k). That is fine for small inputs. The sliding-window lesson on the same problem removes the repeated work by reusing the sum of the previous window.

    On the example, the window sums are 12, 9, 9, 14, 16 and 13, for starts 0 through 5. The best is 16 at start 4, so the answer is [4, 6].

    Three details of the specification decide how the code is written. The window has exactly k elements, so a shorter run at the end of the array never counts. The result holds indices and not the sum, so the method has to remember where the best window started. And when two windows have the same sum, the earlier one is the answer.

    Step by step

    1. Create maxSum as a var starting at Int.MinValue, the smallest possible Int. Any real window sum is at least that large, so the first window always replaces it, even when all the numbers are negative.
    2. Create answer as a var holding an empty Array[Int]. It will be replaced by the bounds of the best window.
    3. Loop over the window starts with i from 0 to nums.length - k. The last window of length k starts at nums.length - k, and to includes that value, unlike until.
    4. Declare sum as a var equal to 0 inside the loop. It starts from zero for every window, so each window adds up its own elements.
    5. Loop idx from i until i + k. These are the k positions of the window. Because until excludes its upper bound, the loop visits exactly k indices.
    6. Add nums(idx) to sum.
    7. Compare after the inner loop. If sum > maxSum, set maxSum to sum and answer to Array(i, i + k - 1). The comparison is strict, so when two windows tie, the earlier one stays.
    8. Return answer after the loops.

    The solution in Scala

    class Solution {
    def maxSum(nums: Array[Int], k: Int): Array[Int] = {
        var maxSum = Int.MinValue
        var answer = Array[Int]()
        for (i <- 0 to nums.length - k) {
            var sum = 0
            for (idx <- i until i + k) {
                sum += nums(idx)
            }
            if (sum > maxSum) {
                maxSum = sum
                answer = Array(i, i + k - 1)
            }
        }
        return answer
    }
}

    The Scala details worth knowing:

    • to versus until. Both build a range. 0 to 5 is 0, 1, 2, 3, 4, 5, while 0 until 5 stops at 4. The outer loop uses to because the last window start is a valid start. The inner loop uses until because i + k is one past the window.
    • Array[Int]() and Array(i, i + k - 1). The first builds an empty array and the second builds a two-element array whose type, Array[Int], is inferred. Because answer is a var, it can be pointed at a new array whenever a better window is found.
    • A variable named like its method. The local var maxSum has the same name as the method maxSum. Inside the body the name refers to the variable. That is legal in Scala, but a different name would be easier to read.
    • Indexing with parentheses. nums(idx) reads an element. Square brackets are for type parameters.
    • Return value. The method returns an Array[Int] of two numbers, the first and the last index of the window, not the sum.

    Complexity

    Time: O(n * k). There are n - k + 1 windows and each one adds k numbers. When k is close to n, the number of windows is small, so the product is largest around k = n / 2, where it is about n^2 / 4.

    Space: O(1). The answer array always has two elements, and the other variables are single integers.

    Edge cases and common mistakes

    • Window the size of the array. For [4, 2] with k = 2 there is one window, starting at 0, and the result is [0, 1]. The range 0 to 0 still runs once, which is why the outer loop uses to.
    • All numbers negative. For [-3, -1, -2] with k = 1 the result is [1, 1]. Starting maxSum at 0 would never accept any window and would return an empty array.
    • Ties. For [1, 1, 1] with k = 2, both windows sum to 2, and the strict > keeps the first, giving [0, 1].
    • k = 1. Each window is one element, and the start and the end of the window are the same index: [7] gives [0, 0].
    • The end index. It is i + k - 1, not i + k. A window of 3 starting at 4 ends at 6.
    • k larger than the array. Then nums.length - k is negative and the range is empty, so the method returns an empty array. The lesson's inputs keep k within the array's length.

    Testing

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