K Items With the Maximum Sum
EasyPrompt
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:
numOnesitems with1s written on them.numZeroesitems with0s written on them.numNegOnesitems 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 + numNegOnes
Approaches
3 approaches with complexity analysis and trade-offs.
This approach simulates the problem by creating a list of all available items, already in descending order of value, and then summing up the first k items.
Algorithm
-
- Create a new list called
items.
- Create a new list called
-
- Add the number
1to theitemslistnumOnestimes.
- Add the number
-
- Add the number
0to theitemslistnumZerostimes.
- Add the number
-
- Add the number
-1to theitemslistnumNegOnestimes.
- Add the number
-
- Initialize a variable
sumto 0.
- Initialize a variable
-
- Iterate from
i = 0tok-1.
- Iterate from
-
- In each iteration, add the value of
items.get(i)tosum.
- In each iteration, add the value of
-
- Return
sum.
- Return
Walkthrough
To find the maximum sum, we should always pick items with the highest value first. The values available are 1, 0, and -1.
This method involves constructing an actual list of all the numbers available in the bag. We can add the items in descending order of their values to avoid a separate sorting step.
- We add
numOnesinstances of1, thennumZerosinstances of0, and finallynumNegOnesinstances of-1to a list. - This list is now effectively sorted by value in descending order.
- Finally, we iterate through the first
kelements of this list and calculate their sum. This sum will be the maximum possible sum.
import java.util.ArrayList;import java.util.List; class Solution { public int kItemsWithMaximumSum(int numOnes, int numZeros, int numNegOnes, int k) { List<Integer> items = new ArrayList<>(); for (int i = 0; i < numOnes; i++) { items.add(1); } for (int i = 0; i < numZeros; i++) { items.add(0); } for (int i = 0; i < numNegOnes; i++) { items.add(-1); } int sum = 0; for (int i = 0; i < k; i++) { sum += items.get(i); } return sum; }}Complexity
Time
O(N), where N is the total number of items (`numOnes + numZeros + numNegOnes`). Creating the list takes O(N) time. Summing the first `k` elements takes O(k) time. Since `k <= N`, the total time is dominated by list creation, making it O(N).
Space
O(N), where N is the total number of items (`numOnes + numZeros + numNegOnes`). We need to store all N items in a list.
Trade-offs
Pros
Very intuitive and easy to understand.
Directly models the problem statement.
Cons
Inefficient in terms of both time and space.
Unnecessary creation of a large data structure for a simple problem.
This approach simulates the process of picking k items greedily without actually creating a list of all items. It iterates k times, and in each step, it picks the best available item.
Algorithm
-
- Initialize
sum = 0.
- Initialize
-
- Loop
ktimes, fromi = 0tok-1.
- Loop
-
- Inside the loop, check if
numOnes > 0.
- Inside the loop, check if
-
- If true, add 1 to
sumand decrementnumOnes.
- If true, add 1 to
-
- Else, check if
numZeros > 0.
- Else, check if
-
- If true, just decrement
numZeros(as adding 0 doesn't change the sum).
- If true, just decrement
-
- Else (meaning we must pick a -1), subtract 1 from
sumand decrementnumNegOnes.
- Else (meaning we must pick a -1), subtract 1 from
-
- After the loop finishes, return
sum.
- After the loop finishes, return
Walkthrough
To maximize the sum, we should always pick items with the highest value first. The greedy strategy is to pick 1s, then 0s, then -1s.
We can simulate this process with a loop that runs k times.
- We maintain a running
sumand keep track of the remaining counts ofnumOnes,numZeros, andnumNegOnes. - In each of the
kiterations, we decide which item to pick:- If there are any
1s left (numOnes > 0), we pick a1. We add 1 to thesumand decrementnumOnes. - Otherwise, if there are any
0s left (numZeros > 0), we pick a0. The sum remains unchanged, and we decrementnumZeros. - Otherwise, we must pick a
-1. We subtract 1 from thesumand decrementnumNegOnes.
- If there are any
- After
kiterations, thesumwill hold the maximum possible value.
class Solution { public int kItemsWithMaximumSum(int numOnes, int numZeros, int numNegOnes, int k) { int sum = 0; for (int i = 0; i < k; i++) { if (numOnes > 0) { sum += 1; numOnes--; } else if (numZeros > 0) { // sum += 0; numZeros--; } else { sum -= 1; numNegOnes--; } } return sum; }}Complexity
Time
O(k), as the loop runs exactly `k` times, and each operation inside the loop is constant time.
Space
O(1), as we only use a few variables to store the counts and the sum, regardless of the input size.
Trade-offs
Pros
More efficient than the simulation with list creation approach.
Constant space complexity.
Cons
Still uses a loop, which is unnecessary for this problem.
Can be slightly slower than a direct mathematical calculation if
kis large.
This is the most optimal approach. It uses a greedy strategy to directly calculate the maximum sum using conditional logic and arithmetic operations, completely avoiding any loops or extra data structures.
Algorithm
-
- Check if
kis less than or equal tonumOnes.
- Check if
-
- If true, it means we only pick items with value
1. The maximum sum isk. Returnk.
- If true, it means we only pick items with value
-
- Else, check if
kis less than or equal tonumOnes + numZeros.
- Else, check if
-
- If true, it means we pick all
numOnesitems and the rest are0s. The maximum sum isnumOnes. ReturnnumOnes.
- If true, it means we pick all
-
- Else, it means we pick all
numOnesitems, allnumZerositems, and the rest must be-1s.
- Else, it means we pick all
-
- The number of
-1s to pick isk - numOnes - numZeros.
- The number of
-
- The total sum is
numOnes - (k - numOnes - numZeros). Return this value.
- The total sum is
Walkthrough
The core idea is to determine how many items of each type (1, 0, -1) will be picked based on the greedy strategy, and then calculate the sum directly.
- Step 1: Pick Ones. We prioritize picking items with value
1. We can pick at mostnumOnesof them. So, we pickmin(k, numOnes)items. These contributemin(k, numOnes)to the sum. We then updatekto reflect the remaining items to be picked. - Step 2: Pick Zeros. If we still need to pick more items (
k > 0), we move to items with value0. Picking0s does not change the sum. We pickmin(k, numZeros)zeros and updatek. - Step 3: Pick Negative Ones. If
kis still greater than 0, we have no choice but to pick items with value-1. We must pickknegative ones. These will decrease the sum byk.
This logic can be simplified into a set of if-else conditions.
class Solution { public int kItemsWithMaximumSum(int numOnes, int numZeros, int numNegOnes, int k) { if (k <= numOnes) { // We can pick k items, and all of them will be 1s. return k; } else if (k <= numOnes + numZeros) { // We pick all numOnes 1s, and the rest are 0s. // The sum is just the number of 1s. return numOnes; } else { // We pick all numOnes 1s, all numZeros 0s. // The remaining items must be -1s. // Number of -1s to pick = k - numOnes - numZeros // Sum = numOnes * 1 + numZeros * 0 + (k - numOnes - numZeros) * -1 return numOnes - (k - numOnes - numZeros); } }}An even more compact way to write this:
class Solution { public int kItemsWithMaximumSum(int numOnes, int numZeros, int numNegOnes, int k) { int sum = 0; // Take as many ones as possible int onesToTake = Math.min(k, numOnes); sum += onesToTake; k -= onesToTake; if (k == 0) return sum; // Take as many zeros as possible int zerosToTake = Math.min(k, numZeros); k -= zerosToTake; if (k == 0) return sum; // Take remaining from negative ones int negOnesToTake = Math.min(k, numNegOnes); sum -= negOnesToTake; return sum; }}Complexity
Time
O(1), as the solution involves a few conditional checks and arithmetic operations, which take constant time.
Space
O(1), as no extra space proportional to the input size is used.
Trade-offs
Pros
The most efficient solution possible.
Extremely fast and requires minimal memory.
Cons
The logic might be slightly less intuitive at first glance compared to a direct simulation.
Solutions
Solution
public class Solution { public int KItemsWithMaximumSum(int numOnes, int numZeros, int numNegOnes, int k) { if (numOnes >= k) { return k; } if (numZeros >= k - numOnes) { return numOnes; } return numOnes - (k - numOnes - numZeros); }}class Solution {public int kItemsWithMaximumSum(int numOnes, int numZeros, int numNegOnes, int k) { if (numOnes >= k) { return k; } if (numZeros >= k - numOnes) { return numOnes; } return numOnes - (k - numOnes - numZeros); }}class Solution {public: int kItemsWithMaximumSum(int numOnes, int numZeros, int numNegOnes, int k) { if (numOnes >= k) { return k; } if (numZeros >= k - numOnes) { return numOnes; } return numOnes - (k - numOnes - numZeros); }};class Solution: def kItemsWithMaximumSum(self, numOnes: int, numZeros: int, numNegOnes: int, k: int) -> int: if numOnes >= k: return k if numZeros >= k - numOnes: return numOnes return numOnes - (k - numOnes - numZeros)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.