LESSON 245 OF 414 · PARTIAL SUMS #2

Remove Min Sum II in Rust: O(n) with a Sliding Window

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 12

Guided

Ctrl + Enter to check

Remove Min Sum Ii in Rust, explained

Problem overview

The function remove_min_sum receives a vector of integers, nums, and a number k. It must pick exactly k numbers, some from the beginning of the vector and some from the end (possibly all from one side), so that their sum is as small as possible, and return that sum.

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, which is the smallest sum possible, so the answer is -5.

Approach: keep the best middle block instead

Picking i numbers from the front and k - i from the back, for every i from 0 to k, works but needs a sum for each choice. There is a neater way to see it. Whatever you pick comes from the two ends, so the numbers you do not pick form one contiguous block in the middle, of length n - k.

The sum of the picked numbers is the total sum minus the sum of that middle block. To make the picked sum as small as possible, make the middle block's sum as large as possible. The problem becomes: find the contiguous block of exactly n - k numbers with the maximum sum, and return total_sum - max_sum.

A sliding window finds that block in one pass. Keep the sum of the current window, add the new number as the window moves right, and when the window is full, record its sum and drop the oldest number. Each step costs constant time.

In the example, n = 8 and the window length is 4. The total of the vector is 4. The window with the largest sum is [5, 2, -1, 3], which adds up to 9. The answer is 4 - 9 = -5.

Step by step

Store the length of nums in n. It is a usize.
Compute the window length window = n - k as usize. Rust never mixes integer types silently, and k is an i32, so it is converted first. as binds tighter than -, so the conversion applies to k alone.
Declare rolling_sum, a mutable i32 at 0, for the sum of the current window.
Declare total_sum the same way, for the sum of the whole vector.
Declare max_sum as i32::MIN, the smallest i32, so that the first full window always replaces it.
Loop over every index i from 0 to n.
Add nums[i] to total_sum.
Add it to rolling_sum too: the number enters the window.
Test whether the window is full with i + 1 >= window. After visiting index i, i + 1 numbers have been seen. The test is written this way rather than i >= window - 1 because usize values can't go below zero.
Record the window: max_sum becomes the larger of itself and rolling_sum.
Slide the window: subtract the oldest number, at index i + 1 - window, so the next pass adds a new number to a window that is one short.
Return total_sum - max_sum as the last expression, with no semicolon.

The solution in Rust

impl Solution {
    fn remove_min_sum(nums: Vec<i32>, k: i32) -> i32 {
        let n = nums.len();
        let window = n - k as usize;
        let mut rolling_sum: i32 = 0;
        let mut total_sum: i32 = 0;
        let mut max_sum: i32 = i32::MIN;
        for i in 0..n {
            total_sum += nums[i];
            rolling_sum += nums[i];
            if i + 1 >= window {
                max_sum = max_sum.max(rolling_sum);
                rolling_sum -= nums[i + 1 - window];
            }
        }
        total_sum - max_sum
    }
}

The Rust details worth a closer look:

Explicit conversions. k as usize turns an i32 into a usize. A negative k would become a huge number, so the function assumes 0 <= k.
Unsigned arithmetic. n - k as usize can't go below zero. If k were larger than n, an optimized build would wrap around to a huge number and a debug build would panic. Valid input has k <= n.
i32::MIN. Integer types have associated constants for their limits. Starting at the minimum guarantees that any real window sum beats it.
max as a method. max_sum.max(rolling_sum) returns the larger of two i32 values.
Tail expression. A semicolon after total_sum - max_sum would turn it into a statement, and the function would no longer return an i32.
Wrapping. Built with optimizations, as the lessons are, overflow of i32 sums wraps silently. A debug build would panic. The solution assumes sums that fit in an i32.

Complexity

Time: O(n). The loop visits every element once, and each pass does a constant amount of work.

Space: O(1). The function keeps a few integers and does not copy the vector.

Edge cases and common mistakes

k = 0. The window is the whole vector, and the only full window is the last position, so max_sum equals total_sum. The answer is 0, the sum of no numbers.
Negative numbers. The window with the maximum sum may itself be negative, and then the answer is larger than the total. For [5, -1, 4] with k = 1, the windows of length 2 are [5, -1] and [-1, 4], with sums 4 and 3. The total is 8, so the answer is 8 - 4 = 4, which is the 4 at the end.
Initializing max_sum with 0. If every window sum is negative, 0 would never be replaced and the answer would be wrong. i32::MIN avoids this.
Dropping the oldest number too early. The subtraction comes after the sum is recorded. Doing it before would lose the number that is still in the window being measured.
Taking k equal to the length. Then window is 0, the condition holds on the very first pass, and the code subtracts nums[i + 1]. At the last index that is out of bounds, and the function panics. For nums = [4, 4] and k = 2, the correct answer is 8 but this code does not reach it, so the solution assumes k is smaller than the length.
Counting picks from the wrong side. Picks come from both ends, so the answer is never a block of k numbers from the middle.

Testing

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

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

Start learning free