Abstract / Summary

Given a list of item values and an integer k, return the sum of the k largest values.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 60% (100k+ submissions).

Typical patterns to solve this problem:

• Greedy
• Math

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a class Solution with a single method kItemsWithMaximumSum. The method receives four integer parameters: the counts of 1s, 0s, and -1s that are available, together with an integer k that specifies how many items must be selected. The goal is to compute the maximum possible sum of the selected items under the constraint that exactly k items are taken from the multiset consisting of the given numbers of 1s, 0s, and -1s.

The algorithm follows a straightforward greedy reasoning: it prefers the highest-valued elements first, then the neutral elements, and finally the lowest-valued elements only when the selection size exceeds the total of the higher-valued elements. The code is compact, consisting of three conditional branches that directly return the computed sum.

Core Logic

The method begins by checking whether the required number of selections k can be satisfied using only the positive elements (1s). The corresponding snippet is:

if k <= numOnes:
    return k

If k is less than or equal to the count of 1s, the optimal sum is simply k, because each selected item contributes +1 to the total.

When k exceeds the number of 1s but does not exceed the combined count of 1s and 0s, the algorithm selects all available 1s and fills the remaining slots with 0s. This yields a sum equal to the total number of 1s, as the 0s do not affect the sum. The relevant code is:

if k <= numOnes + numZeros:
    return numOnes

If k is larger than the sum of numOnes and numZeros, the selection must include some -1s. At this point the algorithm has already taken all 1s and all 0s, and the remaining selections are forced to be -1s. The number of -1s that must be taken is k - numOnes - numZeros. Since each -1 reduces the total sum by one, the final sum is computed by subtracting this excess from the sum contributed by the 1s:

return numOnes - (k - numOnes - numZeros)

This expression simplifies to 2 * numOnes + numZeros - k, but the original form directly reflects the logical steps of the algorithm.

Edge Cases Handled

The code implicitly handles several boundary conditions without additional checks:

• When k is zero, the first condition k <= numOnes is true, and the method returns 0, which is the correct sum for selecting no items.
• When any of the counts numOnes, numZeros, or numNegOnes are zero, the logic still works because the conditions rely only on the numeric relationships between k and the sums of the counts. For example, if numZeros is zero, the second condition reduces to k <= numOnes, and the third branch correctly accounts for the need to use -1s.
• When k equals the total number of available items (numOnes + numZeros + numNegOnes), the third branch is taken, and the subtraction correctly incorporates all required -1s, yielding the minimum possible sum for the full selection.
• When k exceeds the total number of items, the third branch still produces a result, effectively assuming additional -1s beyond the provided count. Although the problem specification typically guarantees k does not exceed the total, the arithmetic remains well-defined.

Performance Considerations

The implementation executes a constant number of simple integer comparisons and arithmetic operations, regardless of the magnitude of the input values. There are no loops, recursion, or data structures that grow with the input size. Consequently, the runtime is deterministic and minimal, making the method highly efficient for any permissible input range. The direct return statements avoid any unnecessary temporary variables or intermediate collections, contributing to low overhead and fast execution.

Imagine a game where you have three piles of magic cards. One pile has cards with a one on them, one pile has cards with a zero, and one pile has cards with a negative one stuck to them. You want to pick exactly k cards from these piles to get the biggest total score possible.

Since you want the highest score, you should always grab the cards with a one first because they make your total grow. Once those are gone, you should pick the cards with a zero because they do not change your total score at all. If you still need more cards after the ones and zeros are finished, you have to start picking the cards with a negative one, which makes your score go down.

The code looks at how many cards you need to pick and compares that to the piles. If your goal is smaller than the pile of ones, you just take that many ones. If you need more cards than the ones offer, but the ones and zeros together are enough, you just take all the ones and keep your score high. If you are forced to pick even more, the code calculates the impact of those pesky negative ones by subtracting them from your total.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: constant
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	Java	Python		C++				TS
	WalkCCC	Java	Python		C++
	leetcode.ca	Java	Python		C++	C#	Go	Rust	TS
	Progiez	Java	Python		C++
github	charles-wangkai	Java
	fsq				C++
	JoshCrozier			JS
	lkwq007		Python
	varunu28	Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
varunu28	Java

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality