Start learning free

LESSON 214 OF 338 · PARTIAL SUMS #1

Remove Min Sum in Go: 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

GO · PARTIAL SUMS #1

Remove Min Sum in Go, explained

Problem overview

The function removeMinSum receives a slice of integers, nums. You may pick some numbers from the beginning of the slice and some from the end, any amounts including none or all, and the function returns the smallest total you can get. Picking nothing gives 0, so the answer is never above 0.

For nums = [-2, 5, 2, -1, 3, -10, 9, -2] the answer is -5. One way is to pick the first element and the last three: -2 + (-10) + 9 + (-2) = -5. Another is to pick the first six and the last one, which also totals -5.

Approach: a prefix and a suffix

A choice is a prefix of length p plus a suffix of length s, with p + s <= n so that they never share an element. Trying every pair is O(n²) pairs. Prefix sums let us do better.

Fix the prefix length p. Its sum is known from a prefix-sum table. The best suffix to combine with it is the cheapest suffix whose length is at most n - p. If we precompute, for every length j, the minimum suffix sum over lengths 0 to j, that is one lookup. Then one pass over p from 0 to n finds the best combination.

Step by step

  1. Store n, the length of nums.
  2. Build prefix with n + 1 entries. prefix[i] is the sum of the first i elements, and prefix[0] is 0 for picking nothing. Each entry is the previous one plus nums[i].
  3. Build suffix the same way from the end. suffix[j] is the sum of the last j elements, so the element added at step j is nums[n - 1 - j].
  4. Build suffixMin. suffixMin[j] is the smallest of suffix[0] to suffix[j]. It starts at 0 and takes min(suffixMin[j - 1], suffix[j]) for each j from 1 to n.
  5. Start result at 0, the answer for picking nothing.
  6. Loop over prefix lengths p from 0 to n inclusive. At each one, combine prefix[p] with suffixMin[n - p], the best suffix that fits in the remaining n - p elements, and keep the smaller of that and result.
  7. Return result.

The solution in Go

func removeMinSum(nums []int) int {
    n := len(nums)
    prefix := make([]int, n + 1)
    for i := 0; i < n; i++ {
        prefix[i + 1] = prefix[i] + nums[i]
    }
    suffix := make([]int, n + 1)
    for j := 0; j < n; j++ {
        suffix[j + 1] = suffix[j] + nums[n - 1 - j]
    }
    suffixMin := make([]int, n + 1)
    for j := 1; j <= n; j++ {
        suffixMin[j] = min(suffixMin[j - 1], suffix[j])
    }
    result := 0
    for p := 0; p <= n; p++ {
        result = min(result, prefix[p] + suffixMin[n - p])
    }
    return result
}

Go details:

  • make([]int, n + 1) creates a slice of n + 1 zeros. That is why prefix[0], suffix[0] and suffixMin[0] are already 0 and need no assignment.
  • Built-in min. Since Go 1.21, min and max are built into the language and work on ordered types such as int. With Go 1.22, no import or helper function is needed.
  • Slices are indexed with ints. nums[n - 1 - j] reads from the end. Go has no negative indexing, so the position is computed explicitly.
  • Empty input. For an empty slice n is 0, every loop runs zero times except the last, which runs once with p = 0, and the result is 0. len of a nil slice is 0 too.

Worked example

For [-2, 5, 2, -1, 3, -10, 9, -2], the suffix sums are 0, -2, 7, -3, 0, -1, 1, 6, 4. The running minimums suffixMin are 0, -2, -2, -3, -3, -3, -3, -3, -3. The prefix sums are 0, -2, 3, 5, 4, 7, -3, 6, 4. For p = 1 the total is -2 + suffixMin[7], which is -2 + (-3) = -5. For p = 6 it is -3 + suffixMin[2], which is -3 + (-2) = -5. Both give the example's answer, and no prefix does better.

Another way to see it

Whatever you pick from the two ends, the elements you leave behind form one contiguous block in the middle, possibly empty. Minimizing the picked sum is the same as maximizing the sum of that block, because the picked sum is the total minus the block. The solution here doesn't use that fact; it combines a prefix with a suffix directly. The related lesson, Remove Min Sum II, uses the middle block idea with a fixed block size.

Complexity

Time: O(n). There are four passes over the data, each doing constant work per element.

Space: O(n). The three tables have n + 1 entries each.

Edge cases and common mistakes

  • All positive numbers. For [1, 2, 3] every non-empty pick is positive, so the answer is 0.
  • All negative numbers. For [-1, -2] picking everything gives -3, and the function returns -3.
  • Overlap. The suffix length may be at most n - p. Using the global minimum suffix could pick elements the prefix already took. That is why suffixMin is a running minimum indexed by the allowed length.
  • Starting result with a large value. The empty pick is always allowed, so 0 is the right start. Starting higher would be harmless but pointless, and starting lower would be wrong.
  • Using n as the prefix limit. The loop goes up to and including n, so picking the whole slice as a prefix is considered.
  • Middle-heavy slices. For [3, -1, 3] the answer is 0, since removing the middle element alone isn't allowed: you can only take from the two ends.

Testing

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