Is K Items With the Maximum Sum easy or hard?

K Items With the Maximum Sum is classified as an Easy problem with about a 60% acceptance rate. The challenge lies in recognizing that a greedy selection order (1, then 0, then -1) guarantees the optimal sum.

K Items With the Maximum Sum Python/Java solution

In Python or Java, the greedy solution calculates how many 1s can be taken, adjusts k, skips zeros if available, and subtracts the remaining picks if -1 values are required. The implementation is a few lines of arithmetic and conditional checks.

How to solve K Items With the Maximum Sum in O(1)?

Take the minimum of k and the number of items with value 1 and add that to the result. Reduce k accordingly. If selections remain, consume zeros which do not change the sum. Any remaining picks must be -1 values, so subtract the remaining count from the total.

What is the best approach for K Items With the Maximum Sum?

The greedy approach is the optimal solution. Always select items with value 1 first, then 0, and finally -1 until k selections are made. Because the values are strictly ordered, this greedy strategy always produces the maximum possible sum in O(1) time and O(1) space.

Is K Items With the Maximum Sum asked at Google/Amazon/Meta?

Problems of this style frequently appear in interviews at large tech companies because they test greedy reasoning and edge case handling. While this exact question is categorized as Easy, similar counting and greedy optimization problems are common in screening rounds.

What data structure is used in K Items With the Maximum Sum?

No complex data structure is required. The problem only relies on integer counters representing the number of 1s, 0s, and -1s. The solution is based on greedy ordering rather than arrays, hash maps, or trees.

What is the time complexity of K Items With the Maximum Sum?

The optimal greedy solution runs in O(1) time and uses O(1) space because the result can be computed directly using counts of 1s, 0s, and -1s. A simple simulation alternative takes O(k) time since it iterates for each selection.

Description Hints 3 Solution Video 5:55

2600. K Items With the Maximum Sum

Easy60.2% acceptance2 companies

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

Asked at 2 companies

Google Meta

Topics

Greedy Math

Hints open one at a time

Hint 1

It is always optimal to take items with the number 1 written on them as much as possible.

Hint 2

If k > numOnes, after taking all items with the number 1, it is always optimal to take items with the number 0 written on them as much as possible.

Hint 3

If k > numOnes + numZeroes we are forced to take k - numOnes - numZeroes -1s.

5:55

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution