LESSON 236 OF 414 · PARTIAL SUMS #1

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

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

Guided

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. Among all continuous subarrays of length exactly k, it 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 answer is [4, 6]. The window 6, 6, 4 sums to 16, and no other window of three elements does better.

Approach: slide the window instead of re-adding it

The brute-force solution adds up all k elements of every window, which takes O(n * k) time. But two neighbouring windows share k - 1 elements. The window that starts at i differs from the previous one in just two places: it has lost nums(i - 1) on the left and gained nums(i + k - 1) on the right.

So once the first window's sum is known, every later sum comes from the previous one with one subtraction and one addition:

new sum = old sum - nums(i - 1) + nums(i + k - 1)

Each window then costs O(1) and the whole algorithm is O(n). Here are the sums on the example, as the window moves from start 1 to start 5, beginning with 12 for the first window 5, 6, 1:

start i	removed	added	sum
1	5	2	9
2	6	6	9
3	1	6	14
4	2	4	16
5	6	3	13

The largest is 16 at start 4, so the method returns [4, 6].

This trick works because the window length is fixed. The window moves one step at a time, so exactly one element leaves and one enters. The same idea gives fast answers to many questions about every run of k consecutive elements.

Step by step

Create answer as a var holding Array(0, k - 1). The first window is a candidate before any comparison happens. If no later window beats it, it is the answer, so starting with an empty array would return nothing in that case.
Declare sum as a var equal to 0. It will hold the sum of the current window.
Add up the first window. A loop with i from 0 until k adds nums(i) to sum. After it, sum is the sum of the first k elements.
Declare maxSum as a var equal to sum. The first window is the best seen so far.
Declare var i = 1 and start a while loop that runs while i <= nums.length - k. These are the remaining window starts, ending with the last window that fits. The line i += 1 goes at the very bottom of the body.
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.
Compare. If sum > maxSum, update maxSum and set answer to Array(i, i + k - 1). Because the comparison is strict, the earliest window wins a tie.
Return answer as the last expression of the method.

The solution in Scala

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

The Scala details worth knowing:

Two different is. The for loop declares its own i, which exists only inside that loop. The later var i = 1 is a separate variable declared after the loop has finished, so the two don't clash.
Why a while loop. The loop needs a counter that starts at 1 and is changed by hand. A for with a range, for (i <- 1 to nums.length - k), would work just as well. The while version shows the sliding explicitly.
No ++. Scala has no increment operator, so the counter grows with i += 1. Forgetting this line makes the loop run forever.
The array literal's type. Array(0, k - 1) is an Array[Int] because both elements are Int. Assigning Array(i, i + k - 1) later keeps the same type.
Last expression. The line answer is the method's value, so no return is needed.

Complexity

Time: O(n). Building the first sum takes k steps, and the loop then does n - k steps with a constant amount of work each. Every element enters the window once and leaves it at most once.

Space: O(1). The result array has two elements and everything else is a single integer.

Edge cases and common mistakes

Window as long as the array. For [4, 2] with k = 2 the loop condition 1 <= 0 is false from the start, so the first window is returned: [0, 1].
All numbers negative. For [-3, -1, -2] with k = 1, the first window is -3, then -1 beats it, then -2 doesn't. The answer is [1, 1]. Because maxSum starts from the first real window sum and not from 0, negative sums are handled.
Ties. For [1, 1, 1] with k = 2 both windows sum to 2, and the strict > keeps [0, 1].
Off-by-one on the entering element. The element that enters is nums(i + k - 1), the last position of the new window, not nums(i + k). Using i + k reads one position too far and fails with an ArrayIndexOutOfBoundsException at the last window.
The element that leaves. It is nums(i - 1), the first position of the previous window.
Moving the increment. If i += 1 is placed above the sliding line, every index in the update is off by one.

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