Start learning free

LESSON 214 OF 347 · PARTIAL SUMS #1

Remove Min Sum in C#: Prefix Sums and Suffix Minimums

Practice O(n) Homework Read the full explanation

Given an input array of integers, pick some numbers from the beginning of the array and some numbers from the end of the array in such a way that their sum is minimized. Return this minimum sum.

Note: You are allowed to pick 0 numbers, in that case return 0. Or you can pick all numbers.

Example

Input: nums = [-2, 5, 2, -1, 3, -10, 9, -2]
Output: -5
Explanation: You can pick the first and the last 3 numbers
             (-2) + (-10) + 9 + (-2) = -5
             Or you can remove the first 6 and the last one
             (-2) + 5 + 2 + (-1) + 3 + (-10) + (-2) = -5
SOLVE IT YOURSELF
Ctrl + Enter to check

C# · PARTIAL SUMS #1

Remove Min Sum in C#, explained

Problem overview

The method RemoveMinSum receives an int[] nums. You pick some numbers from the beginning of the array and some from the end, and you want the sum of everything you picked to be as small as possible. You may pick nothing, which gives 0, or pick the whole array. The method returns the smallest sum.

In the example, nums = [-2, 5, 2, -1, 3, -10, 9, -2]. Picking the first number and the last three gives -2 + (-10) + 9 + (-2) = -5. Picking the first six and the last one gives -5 too. Nothing does better, so the answer is -5.

Approach: a prefix length plus the best suffix that still fits

A choice is a prefix of length p and a suffix of length q, where p + q <= n so that they don't overlap. The sum is prefix[p] + suffix[q], where prefix[p] is the sum of the first p numbers and suffix[q] is the sum of the last q.

Trying every (p, q) pair would be O(n²). But for a fixed p, the best partner is simply the smallest suffix[q] among all q from 0 to n - p. If you precompute that running minimum once, each prefix length needs one lookup. The whole algorithm is a few linear passes.

The three arrays

  • prefix[p]: the sum of the first p numbers, with prefix[0] = 0.
  • suffix[q]: the sum of the last q numbers, with suffix[0] = 0.
  • suffixMin[q]: the smallest of suffix[0] through suffix[q]. Because suffix[0] is 0, it is never above 0, and it includes the choice of taking nothing from the end.

For the example, prefix is 0, -2, 3, 5, 4, 7, -3, 6, 4, and suffix is 0, -2, 7, -3, 0, -1, 1, 6, 4. Then suffixMin is 0, -2, -2, -3, -3, -3, -3, -3, -3. For p = 1, the prefix sum is -2, and the best suffix of length up to 7 is suffixMin[7] = -3, giving -5. For p = 6, the prefix sum is -3, and the best suffix of length up to 2 is suffixMin[2] = -2, giving -5 again.

Another way to see it

Whatever you don't pick is a contiguous block in the middle of the array, possibly empty. Minimising the picked sum is the same as maximising that middle block's sum, because the two parts always add up to the total. The prefix and suffix formulation here avoids searching for the block and works directly on the ends. The follow-up problem, where exactly k numbers must be picked, uses the middle-block view.

The reason the running minimum is enough: all that matters about the suffix is its sum, and only the smallest one is useful, since a smaller suffix sum never makes the total worse. Allowing any length up to n - p is what the running minimum, rather than a single suffix value, gives you.

Step by step

  1. Prefix sums. Create prefix with n + 1 slots. Slot i + 1 is slot i plus nums[i]. The extra slot at the front holds the empty prefix.
  2. Suffix sums. Create suffix the same way, but add the numbers from the right: slot j + 1 is slot j plus nums[n - 1 - j].
  3. Running minimum. Create suffixMin. Its slot 0 stays 0, and each later slot is the smaller of the previous slot and the matching suffix value.
  4. Combine. Start result at 0, because picking nothing is allowed. For each prefix length p from 0 to n, at most n - p numbers remain for the suffix, so candidate prefix[p] + suffixMin[n - p] is the best total for that p. Keep the smallest with Math.Min.
  5. Return result.

The solution in C#

class Solution {
    public int RemoveMinSum(int[] nums) {
        int n = nums.Length;
        int[] prefix = new int[n + 1];
        for (int i = 0; i < n; ++i)
            prefix[i + 1] = prefix[i] + nums[i];
        int[] suffix = new int[n + 1];
        for (int j = 0; j < n; ++j)
            suffix[j + 1] = suffix[j] + nums[n - 1 - j];
        int[] suffixMin = new int[n + 1];
        for (int j = 1; j <= n; ++j)
            suffixMin[j] = Math.Min(suffixMin[j - 1], suffix[j]);
        int result = 0;
        for (int p = 0; p <= n; ++p)
            result = Math.Min(result, prefix[p] + suffixMin[n - p]);
        return result;
    }
};

C# details worth noticing

  • New arrays start filled with zeros. new int[n + 1] sets every slot to 0, so prefix[0], suffix[0] and suffixMin[0] are already right without any assignment.
  • Loops without braces. Each for here has a single statement as its body, so braces are optional. Adding a second statement later without braces is a classic bug, because only the first one stays in the loop.
  • The trailing semicolon after the class's closing brace is legal in C#, and does nothing.
  • Overflow. The sums are int, and wrap around silently if they pass the int limits. The lesson's inputs are small.

Complexity

Time: O(n). There are four loops, each running at most n + 1 times.

Space: O(n) for the three arrays of n + 1 integers.

Edge cases and common mistakes

  • All numbers positive. Picking anything only adds, so the answer is 0. For [1, 2, 3] the code returns 0.
  • All numbers negative. Picking everything is best. For [-1, -2, -3] the code returns -6.
  • Empty array. Here n is 0, so each array has a single slot holding 0. Only the last loop runs, once, and returns 0.
  • Overlap. The key to the combination step is the index n - p. Using the whole suffix array for every p would let the prefix and the suffix share elements and count them twice.
  • Forgetting the empty choice. Starting result at int.MaxValue, or leaving out slot 0 of the suffix arrays, could force you to pick something even when every number is positive.

Testing

  • [-2, 5, 2, -1, 3, -10, 9, -2] returns -5.
  • [1, 2, 3] returns 0.
  • [-1, -2, -3] returns -6.
Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
Start learning free