LESSON 219 OF 348 · PARTIAL SUMS #2

Remove Min Sum II in TypeScript: Sliding Window in O(n)

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 TypeScript, explained

Problem overview

The method removeMinSum receives an array nums of integers 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 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, and no choice of four numbers from the two ends does better.

Approach: keep the best block in the middle

Whatever you pick from the front and the back, the numbers you don't pick form one continuous block in the middle, of length n - k. The picked sum plus the block's sum is the sum of the whole array. So the picked sum is smallest exactly when the block's sum is largest:

answer = totalSum - (largest sum of a block of length n - k)

That turns the problem into one already seen in this chapter: the maximum sum of a window of fixed length. A sliding window solves it in one pass, because moving the window one step right removes one number and adds one.

On the example, n - k = 4. The total is 4. The windows of four numbers have sums 4, 9, -6, 1 and 0, from left to right, and the best is 9, from [5, 2, -1, 3]. The answer is 4 - 9 = -5. The numbers outside that window are exactly the ones picked: the first one and the last three.

Step by step

Turn k into the window size. Reassign k to nums.length - k. From here on, k is the length of the block that stays.
Declare rollingSum, starting at 0, for the sum of the current window.
Declare totalSum, starting at 0. Adding to it during the same pass saves a second loop.
Declare maxSum as Number.NEGATIVE_INFINITY. It will hold the best window sum, and the first full window must replace it. Starting at 0 would be wrong when every window is negative.
Loop over the indices with i.
Add nums[i] to totalSum.
Add nums[i] to rollingSum, since the new number joins the window.
Wait for a full window. The check is i >= k - 1: the window holds k numbers once index k - 1 has been added.
Record the best. Inside the if, update maxSum with Math.max(maxSum, rollingSum).
Slide on. Still inside the if, subtract nums[i - k + 1], the oldest number of the window, so the next iteration works with k - 1 old numbers plus the new one.
Return totalSum - maxSum: everything outside the best block.

The solution in TypeScript

class Solution {
    removeMinSum(nums: number[], k: number): number {
        k = nums.length - k;
        let rollingSum = 0;
        let totalSum = 0;
        let maxSum = Number.NEGATIVE_INFINITY;
        for (let i = 0; i < nums.length; i++) {
            totalSum += nums[i];
            rollingSum += nums[i];
            if (i >= k - 1) {
                maxSum = Math.max(maxSum, rollingSum);
                rollingSum -= nums[i - k + 1];
            }
        }
        return totalSum - maxSum;
    }
}

Some TypeScript details:

Parameters can be reassigned. k = nums.length - k; overwrites the parameter. Parameters behave like local let variables, and the caller's value is not affected, because numbers are passed by value.
Negative infinity is a number. Number.NEGATIVE_INFINITY has the type number, so maxSum can later hold ordinary sums without any special typing.
Doubles, no wrap-around. TypeScript numbers are 64-bit floating-point values, so sums don't overflow like int in some other languages. Whole numbers stay exact up to 2^53.
Reading the type annotations. nums: number[] is checked by the compiler and removed from the JavaScript it produces, so it doesn't validate anything when the code runs.

Complexity

Time: O(n). A single loop does a constant amount of work per element. Each number enters the window once and leaves it once.

Space: O(1). The method uses a few numbers.

Edge cases and common mistakes

k = 0. Nothing is picked, and the block is the whole array. The only window is the full array, so the method returns totalSum - totalSum, which is 0.
Picking all but one. For [1, 2, 3] and k = 1, the block has two numbers and the best is [2, 3] with sum 5. The answer is 6 - 5 = 1.
Negative numbers. For [5, -4, 5] and k = 2, the best block is a single number, 5, and the answer is 6 - 5 = 1: keep the first 5 and pick -4 and the last 5, or the other way round.
k equal to the array's length. Then the window size becomes 0, which this loop doesn't handle: the condition is true from the first index, and the subtraction reads nums[i + 1]. For [5, -4, 5] and k = 3 it returns 1, although the correct answer is 6, the sum of everything. Handle it up front with an early return of the total in your own code.
Starting maxSum at 0. When every window sum is negative, the result would be wrong.
Checking i >= k. That waits one iteration too long and skips the first window.
Subtracting before recording. If rollingSum -= nums[i - k + 1] came before Math.max, the window would be compared one number short.

Testing

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

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

Start learning free