Problem overview
The function remove_min_sum receives a vector of integers, nums. You may take some numbers from the beginning of the vector and some from the end, and the goal is to make their total as small as possible. Taking none at all is allowed and gives 0, and taking everything is allowed too. The function returns the smallest total.
For nums = [-2, 5, 2, -1, 3, -10, 9, -2] the answer is -5. One way to reach it is the first number and the last three, which give -2 + (-10) + 9 + (-2) = -5. Another is the first six and the last one, with the same total.
Approach: choose a prefix length, then the best suffix
A choice is described by two numbers: how many elements p come from the front, and how many q come from the back. They may not overlap, so p + q <= n. Trying every pair would cost O(n²), or more if each total is added up from scratch.
Two arrays cut this down. The prefix sum prefix[p] is the sum of the first p elements. The suffix sum suffix[q] is the sum of the last q elements. A choice then costs prefix[p] + suffix[q].
For a fixed p, the best q is the one with the smallest suffix[q] among the allowed values, q from 0 to n - p. That is a minimum over the beginning of the suffix array, which one more array, suffix_min, can supply: suffix_min[m] is the smallest of suffix[0] to suffix[m]. So for each p the best total is prefix[p] + suffix_min[n - p], and the answer is the smallest of those.
Another way to see the problem: whatever you pick, the numbers you leave out form one contiguous block in the middle, possibly empty. Minimising the picked total is the same as leaving out the block with the largest sum. The approach below works on the picked side directly, and it never needs to think about the block in the middle.
On the example, n = 8. The three arrays are:
prefix: [0, -2, 3, 5, 4, 7, -3, 6, 4]
suffix: [0, -2, 7, -3, 0, -1, 1, 6, 4]
suffix_min: [0, -2, -2, -3, -3, -3, -3, -3, -3]
For p = 1, the total is prefix[1] + suffix_min[7] = -2 + (-3) = -5. That is the first number plus the last three. For p = 6 it is -3 + suffix_min[2] = -3 + (-2) = -5, the first six plus the last one. No other p gives less, and p = 0 and p = 8 give -3 and 4.
The solution in Rust
impl Solution {
fn remove_min_sum(nums: Vec<i32>) -> i32 {
let n = nums.len();
let mut prefix = vec![0i32; n + 1];
for i in 0..n {
prefix[i + 1] = prefix[i] + nums[i];
}
let mut suffix = vec![0i32; n + 1];
for j in 0..n {
suffix[j + 1] = suffix[j] + nums[n - 1 - j];
}
let mut suffix_min = vec![0i32; n + 1];
for j in 1..=n {
suffix_min[j] = suffix_min[j - 1].min(suffix[j]);
}
let mut result = 0i32;
for p in 0..=n {
result = result.min(prefix[p] + suffix_min[n - p]);
}
result
}
}
How the code works
- Build
prefix. It hasn + 1entries, all starting at 0. Entryi + 1is entryiplusnums[i]. The leading 0 stands for taking nothing from the front. - Build
suffix. The loop adds elements from the back: stepjaddsnums[n - 1 - j], the(j + 1)-th element from the end. Sosuffix[q]is the sum of the lastqelements. - Build
suffix_min. The entry at 0 stays 0, which means taking no elements from the back. Each later entry is the smaller of the previous entry and the current suffix sum, a running minimum. - Combine. For every
pfrom 0 ton, addprefix[p]andsuffix_min[n - p]. The indexn - pcaps the suffix at the elements the prefix left untouched, which is how overlap is avoided. - Start
resultat 0, the value for picking nothing, and keep the smaller value. The answer is therefore never positive.
The Rust details worth a closer look:
- Allocating with
vec![0i32; n + 1]. It createsn + 1zeros. Because the vectors start filled, the loops can assign toprefix[i + 1]by index without pushing. n - 1 - j. These areusizevalues. Sincejruns from 0 ton - 1, the result stays betweenn - 1and 0 and never goes below zero.minas a method.suffix_min[j - 1].min(suffix[j])returns the smaller of twoi32values.- Inclusive ranges.
0..=nand1..=nincluden, which is needed because the arrays haven + 1entries. - Overflow. The sums are
i32. In an optimized build, a total beyond thei32range wraps silently; a debug build panics.
Complexity
Time: O(n). There are four loops, each one pass over the vector or over an array of n + 1 entries.
Space: O(n). The three helper arrays each have n + 1 entries. The suffix sums could be replaced by a single running sum to save memory, but the arrays keep each step easy to follow.
Edge cases and common mistakes
- All numbers positive.
[1, 2, 3]returns 0, because taking nothing beats every other choice. This is whyresultstarts at 0. - All numbers negative.
[-1, -2, -3]returns -6: take everything. - Negative numbers in the middle only.
[5, -1, 5]returns 0. The -1 can't be reached without also taking a 5. - Overlap. Using the unrestricted minimum of
suffixfor every prefix would let the two groups share elements and count them twice. The indexn - pprevents it. - Mixed values.
[3, -4, 2]returns -2, from the last two numbers, -4 and 2. - An empty vector. It returns 0: the arrays have one entry each and the loops run once.
Testing
[-2, 5, 2, -1, 3, -10, 9, -2]gives-5.[1, 2, 3]gives0.[-1, -2, -3]gives-6.[5, -1, 5]gives0.[3, -4, 2]gives-2.
