Start learning free

LESSON 238 OF 414 · PARTIAL SUMS #1

Remove Min Sum in Scala: Prefix and Suffix Sums in O(n)

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 pick the first 6 and the last one
             (-2) + 5 + 2 + (-1) + 3 + (-10) + (-2) = -5
SOLVE IT YOURSELF
Ctrl + Enter to check

SCALA · PARTIAL SUMS #1

Remove Min Sum in Scala, explained

Problem overview

The method removeMinSum receives an Array[Int] called nums. You pick some numbers from the beginning of the array and some numbers from the end, and you want the total of the picked numbers to be as small as possible. The method returns that minimum total.

Picking nothing is allowed, and then the total is 0. Picking every number is allowed too. A number can't be picked twice, so the picks from the front and the picks from the back can't overlap.

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

Approach: combine prefix sums with suffix minimums

A choice is a pair: p numbers from the front and q numbers from the back, with p + q <= n. Its total is prefix(p) + suffix(q), where:

  • prefix(p) is the sum of the first p elements, and
  • suffix(q) is the sum of the last q elements.

Trying every pair would take O(n^2) time. The faster idea fixes p and asks for the best q directly. For a fixed p, any q from 0 to n - p is allowed, so the best one is the smallest suffix sum among those. Call it suffixMin(n - p), where suffixMin(m) is the smallest of suffix(0), suffix(1), ..., suffix(m). This table is built once, in a single pass, because each entry is the smaller of the previous entry and the new suffix sum.

Then one loop over p from 0 to n takes the minimum of prefix(p) + suffixMin(n - p). Each of the tables has n + 1 entries, where entry 0 stands for picking nothing.

On the example, the prefix sums are 0, -2, 3, 5, 4, 7, -3, 6, 4, and the suffix sums are 0, -2, 7, -3, 0, -1, 1, 6, 4. The suffix minimums are 0, -2, -2, -3, -3, -3, -3, -3, -3. With p = 1 the front pick is -2 and suffixMin(7) is -3. The total -5 is the answer.

Step by step

  1. Store the length in n with val.
  2. Create prefix with Array.fill(n + 1)(0). Entry p will hold the sum of the first p elements, and entry 0 stays 0 for "pick nothing".
  3. Fill prefix in a loop over i from 0 until n: prefix(i + 1) = prefix(i) + nums(i).
  4. Create suffix the same way. Entry q will hold the sum of the last q elements.
  5. Fill suffix with suffix(j + 1) = suffix(j) + nums(n - 1 - j). The element nums(n - 1 - j) is the (j + 1)-th element counted from the end.
  6. Create suffixMin as another array of n + 1 zeros. Its entry 0 is 0, the sum of picking no suffix.
  7. Fill suffixMin for j from 1 to n: each entry is math.min(suffixMin(j - 1), suffix(j)).
  8. Create result as a var starting at 0. Picking nothing is always allowed, so the answer is never above 0.
  9. Loop p from 0 to n and update result with math.min(result, prefix(p) + suffixMin(n - p)). With p elements taken from the front, at most n - p remain for the back.
  10. Return result.

The solution in Scala

class Solution {
    def removeMinSum(nums: Array[Int]): Int = {
        val n = nums.length
        val prefix = Array.fill(n + 1)(0)
        for (i <- 0 until n) {
            prefix(i + 1) = prefix(i) + nums(i)
        }
        val suffix = Array.fill(n + 1)(0)
        for (j <- 0 until n) {
            suffix(j + 1) = suffix(j) + nums(n - 1 - j)
        }
        val suffixMin = Array.fill(n + 1)(0)
        for (j <- 1 to n) {
            suffixMin(j) = math.min(suffixMin(j - 1), suffix(j))
        }
        var result = 0
        for (p <- 0 to n) {
            result = math.min(result, prefix(p) + suffixMin(n - p))
        }
        return result
    }
}

The Scala details worth knowing:

  • Array.fill(n + 1)(0) creates an array of n + 1 elements, all 0. The first parentheses hold the size and the second hold the value. The array is mutable, so prefix(i + 1) = ... assigns to an element even though prefix is a val. The val stops the name from being re-pointed at another array, not the contents from changing.
  • Assignment looks like a call. prefix(i + 1) = value is how Scala writes an array element update.
  • until versus to. The loops that read nums use until n, since valid indices stop at n - 1. The loops over the n + 1-element tables use 1 to n and 0 to n, because n is a valid index in those arrays.
  • Index arithmetic from the end. nums(n - 1 - j) walks backwards from the last element as j grows.

Complexity

Time: O(n). There are four separate loops, each doing a constant amount of work per step.

Space: O(n). Three arrays of n + 1 integers are stored.

Edge cases and common mistakes

  • All numbers positive. [1, 2, 3] gives 0: picking nothing is best.
  • All numbers negative. [-1, -2, -3] gives -6, from picking all of them.
  • A bad number in the middle. For [5, -3, 5] the answer is 0. The -3 can't be reached without picking a 5 on one side of it.
  • Overlap. The front and back picks must not share an element. This is why the loop pairs prefix(p) with suffixMin(n - p) and not the overall minimum of the suffix table.
  • The starting value of result. It starts at 0 because picking nothing is allowed and gives 0. Starting at a value below the real answer, such as a negative constant, would give wrong results.
  • Forgetting the empty pick. If the tables had no 0 entry at index 0, the case "only from the front" or "only from the back" would be lost.
  • An empty array. It gives 0, as all the tables have one entry holding 0.

Testing

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