Watch 10 video solutions for K Items With the Maximum Sum, a easy level problem involving Math, Greedy. This walkthrough by Programming Live with Larry has 355 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 500 <= k <= numOnes + numZeros + numNegOnesProblem Overview: You are given counts of items with values 1, 0, and -1. You must pick exactly k items to maximize the total sum. Since the values are fixed and limited to three types, the goal is simply choosing the best combination in the right order.
Approach 1: Simulation Approach (O(k) time, O(1) space)
This method simulates the selection process step by step. Always pick from the most valuable items first: 1, then 0, and finally -1. Iterate up to k selections, decreasing the available count of each category while adding its value to the running sum. This approach mirrors how you would manually choose items and works well when explaining the logic during interviews.
The algorithm checks if a 1 is still available and selects it because it increases the sum. When no ones remain, it chooses 0 since it keeps the sum unchanged. Only when both 1 and 0 are exhausted do you select -1. The logic follows a straightforward greedy preference but performs explicit iteration for each pick.
Approach 2: Greedy Approach (O(1) time, O(1) space)
The optimal solution uses a direct greedy calculation instead of simulating each pick. Since 1 > 0 > -1, the maximum sum is obtained by taking as many 1s as possible first. If k is less than or equal to the count of ones, the result is simply k. Otherwise, take all ones and reduce k accordingly.
Next, consume zeros if they exist. They do not change the sum but help reach the required k. Only when both ones and zeros are exhausted do negative values contribute to the result. The final adjustment subtracts the remaining selections because each -1 decreases the sum by one.
This approach works because the value set is small and ordered. A greedy choice is always optimal since taking a higher value earlier never blocks a better future choice. The reasoning aligns with common patterns in greedy algorithms and simple counting problems often seen in math-based interview questions.
Recommended for interviews: The greedy approach is what interviewers expect. It reduces the problem to simple arithmetic and runs in constant time. Showing the simulation first demonstrates understanding of the selection order, but deriving the direct greedy formula shows stronger problem-solving skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulation | O(k) | O(1) | Useful for explaining the step-by-step selection logic or when teaching greedy reasoning. |
| Greedy Calculation | O(1) | O(1) | Best for interviews and production code. Direct arithmetic avoids iteration. |