Abstract / Summary

Given items with values and labels, pick at most one item from each label to get the largest total value.

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 64% (70k+ submissions).

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 implementation solves the problem of selecting up to numWanted elements from two parallel arrays, values and labels, while respecting a per-label usage limit useLimit. It returns the maximum possible sum of the chosen values. The algorithm relies on a max-heap to always consider the largest remaining value and a hash map to keep track of how many times each label has been used.

Key Steps

Building a max-heap of value-label pairs

The first loop iterates over the paired elements of values and labels. For each pair the value is negated and pushed onto a heap, turning Python’s default min-heap into a max-heap.

all = []
for v, l in zip(values, labels):
    heappush(all, (-v, l))   # max-heap: store negative value

Negating the value allows the heap to return the largest original value when heappop is called.

Tracking how many times each label has been used

A defaultdict(int) called have records the count of selections for each label. Because it defaults to zero, the code can safely increment counts without explicit initialization.

have = defaultdict(int)

Selecting values while respecting constraints

The main loop extracts the current largest candidate from the heap, checks the label’s usage against useLimit, and either discards the candidate or adds its value to the result. The loop stops when either the heap is empty or the required number of elements (numWanted) has been selected.

result = 0
count  = 0
while all and count < numWanted:
    v, l = heappop(all)
    if have[l] == useLimit:
        continue

    v = -v                     # restore original positive value
    have[l] += 1
    count   += 1
    result  += v

When a label has already reached its allowed quota, the candidate is ignored and the loop proceeds to the next heap element. The continue statement ensures that no other state changes occur for that iteration.

Finally, the accumulated sum is returned.

return result

Edge Cases Handled

When values and labels are empty, the initial heap construction yields an empty list, causing the while condition to fail immediately and the function returns 0.

If numWanted is 0, the loop condition count < numWanted is false from the start, so no heap operations are performed and the result remains 0.

A useLimit of 0 forces the if have[l] == useLimit check to be true for every label, causing every popped element to be skipped. The loop eventually empties the heap without adding to the result, again returning 0.

When multiple entries share the same label, the have map correctly aggregates their usage count, preventing the selection of more than useLimit items for that label.

If numWanted exceeds the total number of available elements, the loop continues until the heap is exhausted, guaranteeing that all feasible items are considered.

Performance Optimizations

The use of a heap ensures that the algorithm always processes the next highest value without scanning the entire list, which reduces the amount of work needed to find the optimal subset.

Negating values once during insertion avoids repeated sign changes inside the main loop, keeping the inner logic lightweight.

The defaultdict provides O(1) average-time updates and lookups for label counts, eliminating the need for explicit existence checks.

Early termination when count reaches numWanted prevents unnecessary heap operations once the required number of elements has been gathered.

Skipping over elements whose label quota is already met (continue) avoids unnecessary arithmetic on those items, allowing the loop to focus only on viable candidates.

Imagine a big toy box filled with treasures. Each toy has two things written on it: how much fun it is, which is the value, and what kind of toy it is, which is the label. The goal is to pick the most fun toys to play with, but there is a rule that says you cannot pick too many of the same kind of toy.

First, all the toys are lined up from the most fun to the least fun. A special machine helps sort them so that the best toys are always sitting right on top.

Next, it is time to start picking. The process looks at the toy on top and checks if the rule about the labels is okay. If there are still spots left for that kind of toy, it gets taken out of the box.

Every time a toy is picked, the fun points are added up, and the number of toys picked so far goes up by one. If a toy is the same kind as ones already picked and the limit has been reached, the toy is skipped, and the search moves on to the next best one. This keeps happening until either the toy box is empty or the right number of toys has been chosen.

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

Time: loglinear
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	C++	Python		Java			TS
	WalkCCC	C++
	leetcode.ca	C++	Python		Java		Go	TS
	LeetcodeHelp	C++	Python		Java
	Progiez	C++	Python		Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis			JS
	fsq	C++
	Garvit244		Python
	JoshCrozier			JS
	lkwq007		Python
	suxrobGM					C#
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
Garvit244	Python
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#

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