LESSON 242 OF 414 · PARTIAL SUMS #2

Remove Min Sum II in Scala: Sliding Window and Total Sum

Given an input array of integers and a number k, pick exactly k numbers, some from the beginning of the array and some from the end of it, in such a way that their sum is minimized. Return this minimum sum.

Example

Input: nums = [-2, 5, 2, -1, 3, -10, 9, -2], k = 4
Output: -5
Explanation: Pick the first and the last three numbers
             (-2) + (-10) + 9 + (-2) = -5

STEP 1 OF 11

Guided

Ctrl + Enter to check

Remove Min Sum Ii in Scala, explained

Problem overview

The method removeMinSum receives an array nums and a number k. You must pick exactly k numbers, some from the beginning of the array and some from the end, so that their sum is as small as possible. The method returns that smallest sum. The picked numbers may all come from one end, or be split between the two.

In the example, nums = [-2, 5, 2, -1, 3, -10, 9, -2] and k = 4. Taking the first number and the last three gives (-2) + (-10) + 9 + (-2) = -5, and no other choice of four end numbers does better.

Approach: keep the best block in the middle

A direct solution tries every split: take a numbers from the front and k - a from the back, for each a from 0 to k. That works, but there is a neater way to see the problem.

Whatever you pick from the two ends, the numbers you leave behind form one contiguous block in the middle, and that block has exactly nums.length - k numbers. The picked numbers and the block always add up to the total of the array. So the picked sum is total - block, and it is smallest when the block's sum is largest.

The problem becomes: find the maximum sum of a window of fixed length nums.length - k, then subtract it from the total. A sliding window does that in one pass. Instead of re-adding the window's numbers every time, add the number entering the window and subtract the one leaving it.

On the example, the window length is 4. The five blocks of four have sums 4, 9, -6, 1 and 0, so the best one is [5, 2, -1, 3] with sum 9. The total of the array is 4, so the answer is 4 - 9 = -5.

Step by step

Compute the window length. It is nums.length - k, the count of numbers left unpicked. It gets a new name, window, because Scala parameters can't be reassigned, and a val is right since it never changes.
Keep a running sum of the current window in a var named rollingSum, starting at 0.
Keep the total of the whole array in totalSum. Adding to it inside the same loop avoids a second pass.
Start maxSum at Int.MinValue. Every window should be able to replace it, including windows with negative sums. Starting at 0 would give wrong answers whenever all windows are negative.
Loop over every index with for (i <- 0 until nums.length). The range excludes its upper bound.
Add nums(i) to totalSum and to rollingSum. Scala indexes arrays with parentheses.
Wait until the window is full. The first full window ends at index window - 1, so the test is i >= window - 1.
Record the window's sum with math.max(maxSum, rollingSum).
Slide forward. Subtract nums(i - window + 1), the oldest number in the window, so the next iteration's addition produces the next window's sum.
Return totalSum - maxSum after the loop: everything outside the best window.

The solution in Scala

class Solution {
    def removeMinSum(nums: Array[Int], k: Int): Int = {
        val window = nums.length - k
        var rollingSum = 0
        var totalSum = 0
        var maxSum = Int.MinValue
        for (i <- 0 until nums.length) {
            totalSum += nums(i)
            rollingSum += nums(i)
            if (i >= window - 1) {
                maxSum = math.max(maxSum, rollingSum)
                rollingSum -= nums(i - window + 1)
            }
        }
        return totalSum - maxSum
    }
}

The Scala details worth a closer look:

val and var. window never changes, so it is a val. The three sums change, so they are vars.
0 until nums.length is a range that stops before the length. 0 to nums.length would include the length and read past the end of the array.
math.max takes two numbers and returns the larger. It needs no import.
return. The lesson ends with return totalSum - maxSum. In Scala the last expression of a method is its result, so writing just totalSum - maxSum would do the same.
Int is 32 bits. Sums that exceed about 2.1 billion wrap around silently. Long would be the safer choice for very large inputs, but the lesson's method signature uses Int.

Complexity

Time: O(n). The loop visits each index once and does a constant amount of work per index.

Space: O(1). The method uses four integer variables and no extra arrays.

Edge cases and common mistakes

k = 0. Nothing is picked, so the sum is 0. The window covers the whole array and the method returns totalSum - totalSum, which is 0. For [1, 2, 3] it returns 0.
k equal to the length. The window length is 0, and the code reads nums(i - window + 1), which is nums(i + 1). At the last index that is out of bounds, so removeMinSum(Array(5, -4, 3), 3) throws ArrayIndexOutOfBoundsException. The method works for k from 0 up to nums.length - 1; a version that must accept k == nums.length would return the total of the array directly in that case.
All negative numbers. For [-1, -2, -3] and k = 1 the method returns -3. That is correct, and it is why maxSum starts at Int.MinValue.
Wrong window length. Using k as the window length answers a different question: it finds the best block in the middle instead of the picks at the ends.
Forgetting to subtract the old number. The rolling sum would keep growing and would stop describing a window of fixed length.
Checking i >= window. That skips the first full window, which ends at index window - 1.

Testing

nums = [-2, 5, 2, -1, 3, -10, 9, -2], k = 4 gives -5.
nums = [1, 2, 3], k = 2 gives 3.
nums = [1, 2, 3], k = 0 gives 0.
nums = [-1, -2, -3], k = 1 gives -3.

Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free