LESSON 219 OF 348 · PARTIAL SUMS #2

Remove Min Sum II in Kotlin: Sliding Window on the Complement

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

KOTLIN · PARTIAL SUMS #2

Remove Min Sum Ii in Kotlin, explained

Problem overview

The function removeMinSum receives an IntArray called nums and a number k. It 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, and return that sum. Either side can contribute zero numbers.

In the example, nums = [-2, 5, 2, -1, 3, -10, 9, -2] and k = 4. Picking the first number and the last three gives -2 + (-10) + 9 + (-2) = -5, and no other way of picking four numbers from the two ends does better.

Approach: keep the best block in the middle

Picking k numbers from the two ends leaves the other n - k numbers untouched, and those form one contiguous block in the middle. The picked numbers and the block always add up to the total of the array:

picked sum = total - middle block sum

The total is fixed, so the picked sum is smallest exactly when the middle block's sum is largest. The problem becomes: find the contiguous block of n - k numbers with the maximum sum, then subtract it from the total.

That is the sliding-window problem for a fixed window length. Keep the sum of the current window, and each time the window moves one step right, add the new number and subtract the one that left. The total number of operations is linear.

In the example, n = 8 and the window length is 4. The window sums are 4 for [-2, 5, 2, -1], 9 for [5, 2, -1, 3], -6 for [2, -1, 3, -10], 1 for [-1, 3, -10, 9] and 0 for [3, -10, 9, -2]. The largest is 9. The total of the array is 4, so the answer is 4 - 9 = -5.

Step by step

Compute the window length. Declare window with val as nums.size - k. A new name is needed because Kotlin parameters are read-only and k can't be reassigned.
Declare rollingSum with var, starting at 0. It holds the sum of the current window.
Declare totalSum with var, starting at 0. It collects the sum of the whole array while the loop runs, which saves a second pass.
Declare maxSum with var, starting at Int.MIN_VALUE. It holds the best window sum. Starting at 0 would be wrong when every window has a negative sum.
Loop i over nums.indices. Each i is the index where the current window ends.
Add nums[i] to totalSum.
Add nums[i] to rollingSum. The new number joins the window.
Wait for a full window. Write an if that checks i >= window - 1. Before that index, fewer than window numbers have been added.
Inside the if, update maxSum with maxOf(maxSum, rollingSum).
Move to the next window. Still inside the if, subtract nums[i - window + 1] from rollingSum. The window ends at i and holds window numbers, so it starts at i - window + 1, and that number leaves.
Return totalSum - maxSum after the loop.

The solution in Kotlin

class Solution {
    fun removeMinSum(nums: IntArray, k: Int): Int {
        val window = nums.size - k
        var rollingSum = 0
        var totalSum = 0
        var maxSum = Int.MIN_VALUE
        for (i in nums.indices) {
            totalSum += nums[i]
            rollingSum += nums[i]
            if (i >= window - 1) {
                maxSum = maxOf(maxSum, rollingSum)
                rollingSum -= nums[i - window + 1]
            }
        }
        return totalSum - maxSum
    }
}

Walking the example through the loop shows the window at work. At i = 3 the window is full with sum 4, so maxSum becomes 4 and the number at index 0, which is -2, leaves: the rolling sum is 6. At i = 4 the 3 joins to make 9, maxSum becomes 9, and the 5 at index 1 leaves. The remaining windows are smaller, and the function returns 4 - 9 = -5.

The Kotlin details worth a closer look:

Parameters are read-only. Inside a function, a parameter behaves like a val. Writing k = nums.size - k would not compile, so the lesson introduces a new local name.
The order inside the if matters. The window sum is compared first, and the oldest number is removed afterwards. Doing it the other way round would compare a window one number short.
Int.MIN_VALUE as a starting point. It is the smallest Int, -2147483648, so the first full window always replaces it. The final subtraction only happens after at least one window has been seen.
One pass for two sums. totalSum and rollingSum are both updated in the same loop, since each element is read once.
Int arithmetic. Sums wrap silently beyond about 2.1 billion. For inputs that large, Long would be the safe choice.

Complexity

Time: O(n). The loop makes one pass, and each iteration does a constant number of additions, subtractions and comparisons.

Space: O(1). Four integers hold all the state.

Edge cases and common mistakes

k = 0. The window covers the whole array. It becomes full at the last index, maxSum equals the total, and the function returns 0, the sum of picking nothing.
k equals the array length. The window length is 0, and the line rollingSum -= nums[i - window + 1] reads nums[i + 1]. At the last index that is past the end, and the call throws an ArrayIndexOutOfBoundsException. With [1, 2, 3] and k = 3, the answer should be 6, but the code fails. The code is meant for k smaller than the length.
k just below the length. With k = 7 the window holds one number, so the answer is the total minus the largest element: in the example, 4 - 9 = -5.
k = 1. The window has seven numbers and the function returns -2: the two windows of seven numbers sum to 6, and 4 - 6 = -2. The picked number is the first one, -2, or the last one, also -2.
Starting maxSum at 0. If every window sum is negative, 0 would win, and the answer would come out too large.
Using i > window - 1. This would skip the first full window and could miss the best one.
Subtracting the wrong element. The number that leaves is nums[i - window + 1]. Using nums[i - window] would remove the number that has already left, or read before the start of the array.

Testing

nums = [-2, 5, 2, -1, 3, -10, 9, -2], k = 4 gives -5.
The same array with k = 0 gives 0.
The same array with k = 1 gives -2.
The same array with k = 7 gives -5.

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

Start learning free