K Items With the Maximum Sum

Difficulty: Easy | Acceptance: 60.20% | Paid: No Topics: Math, Greedy

There is a bag that consists of numOnes items with value 1, numZeros items with value 0, and numNegOnes items with value -1. You are allowed to pick exactly k items from the bag. Return the maximum possible sum of the values of the items you pick.

• Examples
• Constraints
• Greedy Simulation
• Mathematical Formula

Examples

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 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 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

Greedy Simulation

Intuition To maximize the sum, we should always pick the items with the highest value first. We pick as many 1s as possible, then 0s, and finally -1s if we still need more items.

Steps

• Calculate how many 1s we can take: take_ones = min(k, numOnes). Add this to the sum and subtract from k.
• Calculate how many 0s we can take: take_zeros = min(k, numZeros). Subtract this from k (0s don’t affect the sum).
• The remaining k items must be -1s. Subtract k from the sum.
• Return the final sum.

class Solution:
    def kItemsWithMaximumSum(self, numOnes: int, numZeros: int, numNegOnes: int, k: int) -> int:
        # Take as many 1s as possible
        take_ones = min(k, numOnes)
        k -= take_ones
        
        # Take as many 0s as possible
        take_zeros = min(k, numZeros)
        k -= take_zeros
        
        # The rest are -1s
        return take_ones - k

Complexity

• Time: O(1)
• Space: O(1)
• Notes: This approach is straightforward and efficient.

Mathematical Formula

Intuition We can derive the result directly using arithmetic. The sum is simply the number of 1s picked minus the number of -1s picked. The number of 0s picked acts as a buffer that prevents us from picking -1s.

Steps

• Calculate ones_taken = min(k, numOnes).
• Calculate remaining = k - ones_taken.
• Calculate negs_taken = max(0, remaining - numZeros). This represents how many items are left after taking all available 0s.
• The result is ones_taken - negs_taken.

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

Complexity

• Time: O(1)
• Space: O(1)
• Notes: This is the most optimal solution with constant time operations.