LESSON 215 OF 348 · PARTIAL SUMS #1

Remove Min Sum in TypeScript: 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 remove the first 6 and the last one
             (-2) + 5 + 2 + (-1) + 3 + (-10) + (-2) = -5

SOLVE IT YOURSELF

Ctrl + Enter to check

TYPESCRIPT · PARTIAL SUMS #1

Remove Min Sum in TypeScript, explained

Problem overview

The method removeMinSum receives an array nums of integers. You may pick some numbers from the beginning of the array and some from the end, and the sum of everything picked should be as small as possible. The method returns that minimum sum. Picking nothing is allowed (the sum is then 0), and so is picking the whole array.

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

Approach: a prefix length and a suffix length

A choice is two numbers: p, how many elements to take from the front, and q, how many from the back. They must not take the same element twice, so p + q <= n. The sum is the sum of the first p elements (a prefix sum) plus the sum of the last q elements (a suffix sum).

Trying all pairs (p, q) would cost O(n²), or more if the sums were recomputed. The way to avoid it is to fix p and ask only for the best q. For a fixed p, the allowed values of q are 0 to n - p, and we want the smallest suffix sum among them. That is a running minimum over the suffix sums, so we can precompute it once.

The solution builds three arrays of length n + 1:

prefix[p]: the sum of the first p elements, with prefix[0] equal to 0 for picking nothing.
suffix[q]: the sum of the last q elements, with suffix[0] equal to 0.
suffixMin[q]: the smallest of suffix[0] to suffix[q], the best suffix of at most q elements.

On the example the 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 front gives -2, and suffixMin[7] is -3 (from the last three elements). The total is -5.

Step by step

Store the length in n.
Create prefix with n + 1 zeros. The extra slot at index 0 is the empty prefix.
Fill it: prefix[i + 1] is prefix[i] plus nums[i].
Create suffix the same way. Here suffix[j + 1] adds nums[n - 1 - j], the elements taken from the right end, one more each time.
Create suffixMin, also with n + 1 zeros. Index 0 stays 0, so a suffix of nothing is always an option.
Fill it from index 1: each entry is the smaller of the previous entry and the current suffix value.
Start result at 0, the sum of picking nothing.
Try every prefix length p from 0 to n. The suffix may use at most n - p elements, so the best total for this p is prefix[p] + suffixMin[n - p]. Keep the smaller of that and result.
Return result.

The solution in TypeScript

class Solution {
    removeMinSum(nums: number[]): number {
        const n = nums.length
        const prefix = new Array(n + 1).fill(0)
        for (let i = 0; i < n; ++i)
            prefix[i + 1] = prefix[i] + nums[i]
        const suffix = new Array(n + 1).fill(0)
        for (let j = 0; j < n; ++j)
            suffix[j + 1] = suffix[j] + nums[n - 1 - j]
        const suffixMin = new Array(n + 1).fill(0)
        for (let j = 1; j <= n; ++j)
            suffixMin[j] = Math.min(suffixMin[j - 1], suffix[j])
        let result = 0
        for (let p = 0; p <= n; ++p)
            result = Math.min(result, prefix[p] + suffixMin[n - p])
        return result
    }
}

Some TypeScript details:

Creating a filled array. new Array(n + 1) makes an array of length n + 1 with empty slots, and .fill(0) sets every slot to 0. With a single numeric argument, Array means a length, not an element. Its element type here is any, so the compiler doesn't check what you store. Writing new Array<number>(n + 1).fill(0) would give the arrays the type number[].
No semicolons. JavaScript inserts semicolons automatically at line ends, so this style works. A loop body written on the next line without braces covers only that one statement.
++i and i++. In a for header they do the same thing, since the value of the expression is not used.
Index arithmetic. nums[n - 1 - j] counts from the right end: at j = 0 it is the last element, and at j = n - 1 it is the first.

Complexity

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

Space: O(n). The three arrays each hold n + 1 numbers.

Edge cases and common mistakes

All positive numbers. For [1, 2, 3] the answer is 0, because picking nothing beats every other choice.
All negative numbers. For [-1, -2, -3] the answer is -6: take everything. This is allowed as a prefix with an empty suffix.
The middle can't be picked. For [3, -1, 2] the answer is 0. The -1 sits in the middle, and reaching it would force taking 3 or 2 as well.
Both ends help. For [4, -5, 4] the answer is -1: the first two elements, 4 + (-5).
An empty array. All loops run zero times (the last one runs once, for p = 0) and the result is 0.
Overlap. Taking a prefix of length p and a suffix of more than n - p would count an element twice. That's why the lookup is suffixMin[n - p] and not suffixMin[n].
Starting result too high. Starting result at nums[0] or at a large number would ignore the option to pick nothing.

Testing

[-2, 5, 2, -1, 3, -10, 9, -2] gives -5.
[1, 2, 3] gives 0.
[-1, -2, -3] gives -6.
[4, -5, 4] gives -1.
[] gives 0.

Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free