#2600

Easy

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

K Items With the Maximum Sum

Select k items from a bag containing 1, 0, and -1 to maximize sum using greedy choice and invariant validation strategies.

math greedy

Problem Statement

You are given a bag containing items labeled with numbers 1, 0, or -1. Four integers numOnes, numZeros, numNegOnes, and k describe how many of each item are in the bag and how many items you must pick. Your task is to select exactly k items to achieve the maximum possible sum.

Constraints guarantee that the total number of items equals numOnes + numZeros + numNegOnes, and k will never exceed this total. The optimal approach requires prioritizing items with 1 first, then 0, and finally -1, following a greedy pattern that maintains sum invariance at each step.

Examples

Example 1

Input: numOnes = 3, numZeros = 2, numNegOnes = 0, k = 2

Output: 2

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

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

Solution Approach

Greedy Selection of 1s

Pick as many items labeled 1 as possible, up to k. Each 1 contributes positively, so this first step maximizes the sum directly. Track remaining k after this step for subsequent selections.

Fill Remaining k with 0s

If k is still not reached, take items labeled 0 next. Adding zeros does not change the sum but allows reaching the exact k count without reducing total sum. This step preserves the invariant that sum cannot decrease.

Use -1s Only if Necessary

If k remains after taking all 1s and 0s, select items labeled -1. Each -1 decreases the sum, but picking them is unavoidable if k exceeds the sum of 1s and 0s. Carefully account for their effect on the final sum.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time and space complexity are O(1) because the algorithm involves simple arithmetic and comparisons based on counts rather than iterating over all items.

What Interviewers Usually Probe

Expect candidate to identify the greedy priority of 1 > 0 > -1.
Look for proper handling of k exceeding available 1s and 0s.
Candidate should reason about maintaining sum invariance at each choice.

Common Pitfalls or Variants

Common pitfalls

Assuming the items must be iterated individually instead of using counts.
Forgetting to handle cases where k exceeds numOnes and numZeros.
Misapplying the greedy order and picking -1s too early.

Follow-up variants

Generalizing to items with arbitrary positive, zero, and negative integers.
Changing k dynamically and recalculating maximum sum quickly.
Allowing repeated items and selecting with replacement constraints.

FAQ

What is the main pattern to solve K Items With the Maximum Sum?

The primary pattern is a greedy choice plus invariant validation, always taking 1s first, then 0s, and -1s last.

How do I handle cases when k is larger than numOnes?

After taking all 1s, fill the remaining selection with zeros first, then -1s if necessary.

Does the order of items in the bag affect the maximum sum?

No, only the counts of 1s, 0s, and -1s matter due to the greedy selection strategy.

Can this approach handle negative k values?

No, k is always non-negative and within the total item count as per constraints.

Is it ever optimal to pick a -1 before all 1s and 0s?

No, picking -1s early reduces the sum and violates the greedy invariant needed for maximum sum.

terminal

Solution

Solution 1: Greedy

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$.

1

2

3

4

5

6

7

8

9

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)

Continue Practicing

#2601 prime subtraction operation #2598 smallest missing non negative integer after operations #2607 make k subarray sums equal