Start learning free

LESSON 215 OF 348 · PARTIAL SUMS #1

Remove Min Sum in Kotlin: Prefix Sums and a Suffix Minimum

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

KOTLIN · PARTIAL SUMS #1

Remove Min Sum in Kotlin, explained

Problem overview

The function removeMinSum receives an IntArray called nums. You may pick some numbers from the beginning of the array and some from the end. The picked numbers must be different elements, and the function returns the smallest total they can have. Picking nothing is allowed and gives 0, and picking every number is allowed too.

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 the same -5, so both choices are optimal and the answer is -5.

Approach: a prefix, a suffix and a way to choose the suffix quickly

A choice is described by two numbers: p, how many numbers to take from the front, and q, how many to take from the back. They can't overlap, so p + q <= n, where n is the length of the array. The total of a choice is the sum of the first p numbers plus the sum of the last q numbers.

Computing these sums from scratch for every pair (p, q) would be slow. Two arrays of running totals make each sum a single lookup:

  • prefix[p] is the sum of the first p numbers;
  • suffix[q] is the sum of the last q numbers.

Both have n + 1 entries, because taking zero numbers is a valid choice and its sum is 0.

That still leaves a double loop over p and q. But for a fixed p, the best q is the one with the smallest suffix[q] among q = 0, 1, ..., n - p. Those minima are the same ones every time, just over a growing range, so they can be computed once. Define suffixMin[t] as the smallest value of suffix[q] for q from 0 to t. The best total for a given p is then prefix[p] + suffixMin[n - p], and the answer is the smallest of these over all p.

Everything is built in single passes, so the whole algorithm is linear.

Step by step

  1. Store the length in n with val.
  2. Create prefix as an IntArray(n + 1). It starts filled with zeros, so prefix[0] is already 0.
  3. Fill it in a loop. For each i from 0 to n - 1, set prefix[i + 1] to prefix[i] + nums[i].
  4. Create suffix as another IntArray(n + 1).
  5. Fill it from the back. The j-th number from the end is nums[n - 1 - j], so suffix[j + 1] is suffix[j] + nums[n - 1 - j].
  6. Create suffixMin as a third IntArray(n + 1). Its entry 0 is 0, which is correct, since suffix[0] is 0.
  7. Fill it for j from 1 to n. Each entry is the smaller of the previous minimum and suffix[j].
  8. Declare result with var, starting at 0. Picking no number at all is allowed, so 0 is a candidate answer already.
  9. Try every number of front picks. Loop p from 0 to n inclusive.
  10. Combine. The back picks can number at most n - p, so the best total with p front picks is prefix[p] + suffixMin[n - p]. Keep the smaller of this and result.
  11. Return result.

The solution in Kotlin

class Solution {
    fun removeMinSum(nums: IntArray): Int {
        val n = nums.size
        val prefix = IntArray(n + 1)
        for (i in 0 until n) {
            prefix[i + 1] = prefix[i] + nums[i]
        }
        val suffix = IntArray(n + 1)
        for (j in 0 until n) {
            suffix[j + 1] = suffix[j] + nums[n - 1 - j]
        }
        val suffixMin = IntArray(n + 1)
        for (j in 1..n) {
            suffixMin[j] = minOf(suffixMin[j - 1], suffix[j])
        }
        var result = 0
        for (p in 0..n) {
            result = minOf(result, prefix[p] + suffixMin[n - p])
        }
        return result
    }
}

The Kotlin details worth a closer look:

  • IntArray(size) is zero-filled. The constructor creates an array of that length with every element 0, which is exactly the starting point these running totals need.
  • val arrays are still mutable. val prefix means the name always refers to the same array. The elements of the array can change, which is why prefix[i + 1] = ... is allowed.
  • until versus ... The first two loops use 0 until n because they read nums[i] and need valid indices. The last two use 1..n and 0..n because the arrays have n + 1 entries and the last index, n, is needed.
  • Indices count from the end. In nums[n - 1 - j], j = 0 reads the last element and j = n - 1 reads the first.
  • Empty input works. With n = 0 the first two loops don't run, 1..0 is an empty range, and the final loop runs once for p = 0. The function returns 0.

Complexity

Time: O(n). There are four loops, each with at most n + 1 iterations, and each iteration does a constant amount of work.

Space: O(n). The three arrays have n + 1 entries each. The prefix and suffix totals could be folded into fewer arrays, but the three-array version keeps each idea separate.

Edge cases and common mistakes

  • All positive numbers. Every pick adds to the total, so the best choice is to pick nothing: [1, 2, 3] returns 0.
  • All negative numbers. Every pick lowers the total, so pick everything: [-1, -2, -3] returns -6. This is also where overlap matters. A solution that ignored the limit p + q <= n would take all three numbers from the front and all three from the back and report -12, counting each element twice.
  • Empty array. It returns 0.
  • Negative numbers in the middle. In [3, -4, 5, -1] the -4 is reachable only by also taking the 3 in front of it. The best choice is the first two numbers and the last one: 3 + (-4) + (-1) = -2, so the function returns -2.
  • Skipping the empty suffix. The entry suffixMin[0] stands for taking no numbers from the back. It must stay 0, so that taking only a prefix, or nothing, is always one of the options.
  • Looping p to n - 1. Taking all the numbers from the front is a valid choice and must be tried, which needs p = n.
  • Overflow. The totals are Int values and wrap silently beyond about 2.1 billion.

Testing

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