Skip to main content
Talentd

K Items With the Maximum Sum - Solution & Explanation

EasyMathGreedy19 min readAsked at: Meta, Google
Practice this problem

Problem Statement

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

Approach Overview

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

Approach 1: Greedy Approach

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:

  • First, select all '1' items, up to a maximum of 'k'.
  • If there's a remainder of 'k' after '1's, fill the remaining with '0's from the total available.
  • If '0's are exhausted and there is still a remainder, use '-1's for the rest.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Simulation Approach

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:

  • Create an array containing 'numOnes', 'numZeros', and 'numNegOnes'.
  • Sort the array in descending order.
  • Select the first 'k' items and compute their sum.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: 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.

Thus:

  • If the number of items marked as 1 in the bag is greater than or equal to k, we take k items, and the sum of the numbers is k.
  • If the number of items marked as 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.
  • Otherwise, we take 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).

Code

PythonJavaC++GoTypeScriptRustC#

Python

Java

C++

Go

TypeScript

Rust

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Approach

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.

Simulation Approach

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.

Greedy—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
SimulationO(k)O(1)Useful for explaining the step-by-step selection logic or when teaching greedy reasoning.
Greedy CalculationO(1)O(1)Best for interviews and production code. Direct arithmetic avoids iteration.

Video Solution

2600. K Items With the Maximum Sum (Leetcode Easy) • Programming Live with Larry • 361 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice K Items With the Maximum Sum with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Subarray