Start learning free

LESSON 239 OF 415 · PARTIAL SUMS #1

Remove Min Sum in Swift: Prefix Sums and Suffix Minimums 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

SWIFT · PARTIAL SUMS #1

Remove Min Sum in Swift, explained

Problem overview

The method removeMinSum receives an array of integers. You may pick some numbers from the beginning of the array and some numbers from the end. Picking zero numbers is allowed, and so is picking all of them. The picked numbers add up to some total, and the method returns the smallest total that is possible. Picking nothing gives 0, so the result is never above 0.

In the example [-2, 5, 2, -1, 3, -10, 9, -2] the answer is -5. One way to get it is the first number and the last three: -2 + (-10) + 9 + (-2) = -5. Another is the first six numbers and the last one, which also sum to -5: -2 + 5 + 2 + (-1) + 3 + (-10) + (-2).

Approach: choose p from the front, then the best q from the back

Suppose you take the first p numbers. The picks from the end must not overlap with them, so you can take any number q of final elements as long as p + q <= n. The total is then the sum of the first p numbers plus the sum of the last q numbers.

Trying every pair (p, q) is quadratic, since each pair needs a sum. Two ideas make it linear:

  • Prefix sums. prefix[p] is the sum of the first p numbers, with prefix[0] = 0. Each entry costs one addition on top of the previous one.
  • Suffix sums. suffix[q] is the sum of the last q numbers, with suffix[0] = 0.

For a fixed p, any q from 0 to n - p is allowed, and we want the smallest suffix[q] among them. That is a running minimum, so we precompute suffixMin[j]: the smallest value among suffix[0], suffix[1], up to suffix[j]. Then the best total for a given p is:

prefix[p] + suffixMin[n - p]

and the answer is the smallest of these over all p from 0 to n.

On the example, the three arrays are:

prefix    = [0, -2, 3, 5, 4, 7, -3, 6, 4]
suffix    = [0, -2, 7, -3, 0, -1, 1, 6, 4]
suffixMin = [0, -2, -2, -3, -3, -3, -3, -3, -3]

For p = 1, the total is prefix[1] + suffixMin[7] = -2 + -3 = -5. For p = 6, it is prefix[6] + suffixMin[2] = -3 + -2 = -5. No p does better, so the answer is -5.

Step by step

  1. Store the length in n. It is used for every array size and loop bound.
  2. Create prefix as n + 1 zeros. The extra slot is for the empty prefix.
  3. Fill it: for each i, prefix[i + 1] is prefix[i] plus nums[i].
  4. Create suffix the same way, with n + 1 zeros.
  5. Fill it from the right. For each j, suffix[j + 1] is suffix[j] plus nums[n - 1 - j]. As j grows, n - 1 - j walks from the last element toward the first.
  6. Create suffixMin with n + 1 zeros. Its entry 0 is already right, because suffix[0] is 0.
  7. Fill it from 1 up to n: each entry is the smaller of the previous entry and suffix[j].
  8. Create result at 0. Picking nothing is allowed, so 0 is a valid total, and the result never goes above it.
  9. Loop over p from 0 to n inclusive. For each, take the smaller of result and prefix[p] + suffixMin[n - p].
  10. Return result.

The solution in Swift

class Solution {
    func removeMinSum(_ nums: [Int]) -> Int {
        let n = nums.count
        var prefix = [Int](repeating: 0, count: n + 1)
        for i in 0..<n {
            prefix[i + 1] = prefix[i] + nums[i]
        }
        var suffix = [Int](repeating: 0, count: n + 1)
        for j in 0..<n {
            suffix[j + 1] = suffix[j] + nums[n - 1 - j]
        }
        var suffixMin = [Int](repeating: 0, count: n + 1)
        for j in 1...n {
            suffixMin[j] = min(suffixMin[j - 1], suffix[j])
        }
        var result = 0
        for p in 0...n {
            result = min(result, prefix[p] + suffixMin[n - p])
        }
        return result
    }
}

The Swift details worth knowing:

  • [Int](repeating:count:). This builds an array of count copies of the value, here zeros. The arrays are var because the loops write into them.
  • Closed and half-open ranges. 0..<n visits the indices of nums. 1...n and 0...n include n, which is the last valid index of the arrays of size n + 1.
  • A backwards range crashes. 1...n with n = 0 is the range 1 to 0, and Swift stops with a run-time error. The solution therefore assumes the array is not empty.
  • Bounds are checked. Reading nums[n - 1 - j] outside the array would crash. Here j stays in 0..<n, so the index stays in 0...n - 1.
  • Arithmetic is checked too. Int is 64 bits, and a sum past its range crashes instead of wrapping.

Complexity

Time: O(n). There are four loops, each over at most n + 1 positions, with constant work per step.

Space: O(n). The three arrays hold n + 1 numbers each. It would be possible to cut that down by keeping only running values, but the arrays make each step easy to check.

Edge cases and common mistakes

  • All numbers positive. [1, 2, 3] returns 0, by picking nothing.
  • All numbers negative. [-1, -2] returns -3, picking everything.
  • Overlap. The front and back picks must not share an element. That is why the lookup is suffixMin[n - p], which only covers suffixes of length up to n - p. Looking at all of suffix would count some elements twice.
  • The middle is skipped, not removed one by one. [4, -5, 4] returns -1: take the 4 and the -5 from the front, or the -5 and the 4 from the back. Taking only the -5 is not possible, because it is not at either end.
  • Starting result at Int.max. The empty pick, with total 0, would be missed for all-positive arrays.
  • Forgetting the empty prefix. Arrays of size n instead of n + 1 cannot represent "pick none from the front" or "pick all".

Testing

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