LeetCode 1090: Largest Values From Labels

Problem Restatement

We have n items, each with a value and a label.

We want to choose a subset of items to maximize total value, subject to:

• At most numWanted items can be chosen.
• At most useLimit items with the same label can be chosen.

The official constraints state that n == values.length == labels.length and 1 <= numWanted, useLimit <= n <= 2 * 10^4.

Input and Output

Function shape:

def largestValsFromLabels(values: list[int], labels: list[int], numWanted: int, useLimit: int) -> int:
    ...

Examples

Example 1:

values = [5,4,3,2,1], labels = [1,1,2,2,3], numWanted = 3, useLimit = 1

Best 3 items with at most 1 per label: pick 5 (label 1), 3 (label 2), 1 (label 3). Sum = 9.

Answer:

9

Key Insight

Greedy: sort items by value descending. Pick items greedily, tracking how many of each label we’ve used.

Algorithm

1. Sort (value, label) pairs by value descending.
2. Greedily pick each item if:
   • We haven’t chosen numWanted items yet.
   • The label’s count hasn’t reached useLimit.

Edge Cases

• Duplicates usually matter; store counts when a set would lose necessary multiplicity.
• Update the frequency structure in the same order the invariant assumes.
• Check empty or one-element inputs if the problem allows them.

Complexity

Common Pitfalls

• Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
• Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

from collections import defaultdict

class Solution:
    def largestValsFromLabels(self, values: list[int], labels: list[int], numWanted: int, useLimit: int) -> int:
        items = sorted(zip(values, labels), reverse=True)
        label_count = defaultdict(int)
        total = 0
        chosen = 0

        for val, label in items:
            if chosen == numWanted:
                break
            if label_count[label] < useLimit:
                total += val
                label_count[label] += 1
                chosen += 1

        return total

Testing

def run_tests():
    s = Solution()

    assert s.largestValsFromLabels([5,4,3,2,1], [1,1,2,2,3], 3, 1) == 9
    assert s.largestValsFromLabels([5,4,3,2,1], [1,3,3,3,2], 3, 2) == 12
    assert s.largestValsFromLabels([9,8,8,7,6], [0,0,0,1,1], 3, 1) == 16

    print("all tests passed")

run_tests()