Teaching Kids Programming – K Items With the Maximum Sum

Teaching Kids Programming: Videos on Data Structures and Algorithms

There is a bag that consists of items, each item has a number 1, 0, or -1 written on it. You are given four non-negative integers numOnes, numZeros, numNegOnes, and k.

The bag initially contains:
numOnes items with 1s written on them.
numZeroes items with 0s written on them.
numNegOnes items with -1s written on them.
We want to pick exactly k items among the available items. Return the maximum possible sum of numbers written on the items.

Example 1:
Input: numOnes = 3, numZeros = 2, numNegOnes = 0, k = 2
Output: 2
Explanation: We have a bag of items with numbers written on them {1, 1, 1, 0, 0}. We take 2 items with 1 written on them and get a sum in a total of 2.
It can be proven that 2 is the maximum possible sum.

Example 2:
Input: numOnes = 3, numZeros = 2, numNegOnes = 0, k = 4
Output: 3
Explanation: We have a bag of items with numbers written on them {1, 1, 1, 0, 0}. We take 3 items with 1 written on them, and 1 item with 0 written on it, and get a sum in a total of 3.
It can be proven that 3 is the maximum possible sum.

Constraints:
0 <= numOnes, numZeros, numNegOnes <= 50
0 <= k <= numOnes + numZeros + numNegOnes

Teaching Kids Programming – K Items With the Maximum Sum

We can construct the sorted array, and then pick the K items exactly from the right to the left. This has the time complexity of O(N) where N is the total number (equals to Ones + Zeros + Negative-Ones). And the space complexity is also O(N) as we need to prepare such an array.

1
2
3
4
5
6

class Solution:
    def kItemsWithMaximumSum(self, numOnes: int, numZeros: int, numNegOnes: int, k: int) -> int:
        if k == 0:
            return 0
        a = numNegOnes * [-1] + numZeros * [0] + numOnes * [1]        
        return sum(a[-k:])

class Solution:
    def kItemsWithMaximumSum(self, numOnes: int, numZeros: int, numNegOnes: int, k: int) -> int:
        if k == 0:
            return 0
        a = numNegOnes * [-1] + numZeros * [0] + numOnes * [1]        
        return sum(a[-k:])

A special case is when K is zero, we return 0, otherwise we use the list comprehension to return the sum of the last K numbers of the constructed sorted array (that contains numNegOnes -1, numZeros 0, and numOnes 1).

A faster approach/algorithm would be to compute the ones we have (as we pick them first), then subtract the negative ones which is max(0, k-numZeros-numOnes). If k is exceeding the amount of zeros plus ones, then we have to minus the amount of negative ones. The time/space complexity is O(1) constant.

1
2
3

class Solution:
    def kItemsWithMaximumSum(self, numOnes: int, numZeros: int, numNegOnes: int, k: int) -> int:
        return min(k, numOnes) - max(0, k - numZeros - numOnes)

class Solution:
    def kItemsWithMaximumSum(self, numOnes: int, numZeros: int, numNegOnes: int, k: int) -> int:
        return min(k, numOnes) - max(0, k - numZeros - numOnes)

–EOF (The Ultimate Computing & Technology Blog) —