Scale Engineer

K Items With the Maximum Sum

Easy
#2380Time: 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.
Patterns
MathGreedy

Prompt

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

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

    1. Create a new list called items.
    1. Add the number 1 to the items list numOnes times.
    1. Add the number 0 to the items list numZeros times.
    1. Add the number -1 to the items list numNegOnes times.
    1. Initialize a variable sum to 0.
    1. Iterate from i = 0 to k-1.
    1. In each iteration, add the value of items.get(i) to sum.
    1. Return sum.

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 numOnes instances of 1, then numZeros instances of 0, and finally numNegOnes instances of -1 to a list.
  • This list is now effectively sorted by value in descending order.
  • Finally, we iterate through the first k elements 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.

Solutions

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);    }}

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.

← Previous

Previous problem

Next →

Next problem