Start learning free

LESSON 218 OF 338 · PARTIAL SUMS #2

Remove Min Sum II in Go: Sliding Window on the Middle Block

Practice O(n) Read the full explanation

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
    Ctrl + Enter to check

    GO · PARTIAL SUMS #2

    Remove Min Sum Ii in Go, explained

    Problem overview

    The function removeMinSum receives a slice of integers, nums, and a number k. You must pick exactly k numbers, some from the beginning of the slice and some from the end, so that their sum is as small as possible. The function returns that sum.

    For 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, which is the minimum.

    Approach: keep the best middle block

    Whatever you pick from the two ends, the n - k numbers you leave form one contiguous block in the middle. The picked sum equals the total of the slice minus the sum of that block. So minimizing the picked sum means maximizing the block's sum.

    That turns the task into a familiar one: the maximum sum of a window of fixed length n - k, found with a sliding window in one pass. Trying every split between the beginning and the end would also work, but this view needs no table of prefix sums.

    Step by step

    1. Reassign k to len(nums) - k. From here on k is the window size, the length of the block that stays.
    2. Declare rollingSum as 0. It holds the sum of the current window and is updated instead of recomputed.
    3. Declare totalSum as 0, so the whole-slice sum comes out of the same pass.
    4. Declare maxSum as math.MinInt, the smallest possible int. The first full window then always replaces it, even when all window sums are negative.
    5. Loop over every index i of nums.
    6. Add nums[i] to totalSum.
    7. Add nums[i] to rollingSum, since the new number enters the window.
    8. Check whether the window is full: i >= k-1. Before that, fewer than k numbers have been added.
    9. Update maxSum with max(maxSum, rollingSum).
    10. Slide on: subtract nums[i-k+1], the oldest number of the window, from rollingSum.
    11. Return totalSum - maxSum, the sum of the numbers outside the best block.

    The solution in Go

    func removeMinSum(nums []int, k int) int {
    k = len(nums) - k
    rollingSum := 0
    totalSum := 0
    maxSum := math.MinInt
    for i := 0; i < len(nums); i++ {
        totalSum += nums[i]
        rollingSum += nums[i]
        if i >= k-1 {
            maxSum = max(maxSum, rollingSum)
            rollingSum -= nums[i-k+1]
        }
    }
    return totalSum - maxSum
}

    Go details:

    • Parameters are local copies. k = len(nums) - k changes only this function's own k. Integers are passed by value, so the caller's variable stays as it was.
    • math.MinInt comes from the math package, which the file has to import (import "math"), and exists since Go 1.17. On a 64-bit platform it is -9223372036854775808.
    • Built-in max. Since Go 1.21 the language has built-in min and max for ordered types, so no helper is needed.
    • Reusing a name. The parameter keeps its name k but now means something else. This is compact, but a new variable such as window would be clearer in your own code.

    Worked example

    With 8 numbers and k = 4, the window size is 4. The total of the slice is 4. The five window sums, from left to right, are 4, 9, -6, 1 and 0. The largest is 9, the block [5, 2, -1, 3], so the result is 4 - 9 = -5. The numbers outside that block are -2, -10, 9 and -2, which are the first one and the last three.

    Why this equals the original problem

    The earlier Remove Min Sum lesson lets you pick any number of elements and compares prefix and suffix sums. Here the count is fixed, which is what makes a single fixed-size window enough. Every choice of k elements from the two ends leaves exactly one block of n - k consecutive elements, and every block of that size corresponds to exactly one choice. So scanning all windows of that size covers every possible pick, once each, without ever listing the picks themselves.

    Complexity

    Time: O(n). One pass, with constant work per element.

    Space: O(1). Only a few integers.

    Edge cases and common mistakes

    • Picking nothing. With k = 0 the window is the whole slice, and the result is 0.
    • Picking one number. For the example with k = 1 the answer is -2, the smaller of the two end values (-2 and -2).
    • Picking all but one. With k = 7 the window has one number, the largest value, 9. The result is 4 - 9 = -5.
    • Picking every number. With k equal to len(nums) the window size becomes 0, and the line rollingSum -= nums[i-k+1] reaches nums[i+1], which runs past the end of the slice and panics. If that input is possible, return the plain total before the loop.
    • Starting maxSum at 0. If every window sum is negative, 0 would never be replaced, and the answer would be wrong. That is why math.MinInt is used.
    • Off-by-one on the first full window. The first window ends at index k-1, so the check is i >= k-1, not i >= k.
    • Subtracting the wrong element. The oldest number of a window that ends at i is nums[i-k+1].
    • Forgetting the import. Using math.MinInt in a file without import "math" is a compile error.

    Testing

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