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.
This approach is based on a greedy algorithm that maximizes the sum by prioritizing the selection of items with '1' over '0' and '-1'.
Steps:
This C program defines a function maxSum. First, it checks if 'k' is less than or equal to 'numOnes'. If yes, the sum is 'k', due to selecting all '1' items. If 'k' is more than 'numOnes' but less than 'numOnes + numZeros', the sum is 'numOnes'. Else, subtracting any additional needed items from '-1's give us the final sum.
Time Complexity: O(1) as the operation depends on simple conditional checks.
Space Complexity: O(1) since no extra space is used except for function call variables.
This approach uses simulation by creating an array representation of the items and sorts them. It then picks the first 'k' elements to maximize the sum.
Steps:
Here, an array 'items' is populated with '1's, '0's, and '-1's. qsort is used to sort this in descending order, and then the first 'k' elements are summed.
Time Complexity: O(n log n) for sorting the array where n is the total number of items.
Space Complexity: O(n) for the result item array.
According to the problem description, we should take as many items marked as 1 as possible, then take items marked as 0, and finally take items marked as -1.
Thus:
1 in the bag is greater than or equal to k, we take k items, and the sum of the numbers is k.1 is less than k, we take numOnes items, resulting in a sum of numOnes. If the number of items marked as 0 is greater than or equal to k - numOnes, we take k - numOnes more items, keeping the sum at numOnes.k - numOnes - numZeros items from those marked as -1, resulting in a sum of numOnes - (k - numOnes - numZeros).The time complexity is O(1), and the space complexity is O(1).
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(1) as the operation depends on simple conditional checks. |
| Simulation Approach | Time Complexity: O(n log n) for sorting the array where n is the total number of items. |
| Greedy | — |
| 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. |
2600. K Items With the Maximum Sum (Leetcode Easy) • Programming Live with Larry • 355 views views
Watch 9 more video solutions →Practice K Items With the Maximum Sum with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor