Largest Values From Labels: Greedy Selection with Constraints

You are given two arrays, values and labels, both of length n. Each item i has a value values[i] and a label labels[i]. You are also given two integers, numWanted and useLimit. You need to choose a subset of items such that the subset has at most numWanted items, no label appears more than useLimit times in the subset, and the sum of values in the subset is maximized.

This is LeetCode 1090: Largest Values From Labels, a medium problem that tests your ability to apply greedy selection under frequency constraints. The trick is to sort first, then pick greedily while tracking how many times each label has been used.

Why this problem matters

Largest Values From Labels is a clean example of constrained greedy selection. You want to maximize a sum, but you cannot just take the top numWanted items because some of them might share a label. The label frequency constraint forces you to skip certain high-value items in favor of lower-value items with unused labels.

This pattern appears in real-world scenarios like resource allocation (picking the best projects from different departments with a cap per department), portfolio diversification (limiting exposure to any single sector), and task scheduling (selecting the highest-priority tasks with constraints on task types).

The key insight

When you want to maximize a sum and you have a budget on how many items to pick, sorting by value in descending order and picking greedily is optimal. The label constraint adds a twist, but it does not change the core strategy. You still sort by value descending and iterate through the items in that order. For each item, you check whether its label has room. If the label count is below useLimit, you take the item. If the label is already at the limit, you skip it. You stop as soon as you have picked numWanted items or run out of items to consider.

Why does greedy work here? Because the items are independent. Taking one item does not affect the value of another item. The only interaction is through the label constraint, which acts as a simple counter. Sorting ensures you always consider the most valuable items first, and the label counter ensures you never violate the constraint.

The solution

from collections import defaultdict

def largest_vals_from_labels(values: list[int], labels: list[int], num_wanted: int, use_limit: int) -> int:
    items = sorted(zip(values, labels), reverse=True)
    label_count = defaultdict(int)
    total = 0
    selected = 0

    for value, label in items:
        if label_count[label] < use_limit:
            total += value
            label_count[label] += 1
            selected += 1
            if selected == num_wanted:
                break

    return total

The function starts by zipping values and labels together into pairs, then sorting those pairs in descending order by value. Python's sorted with reverse=True sorts tuples by their first element (value) in descending order, which is exactly what we need.

Next, it initializes a defaultdict called label_count to track how many times each label has been used in the selected subset. The total accumulates the sum of selected values, and selected tracks how many items have been picked so far.

The loop iterates through the sorted items from highest value to lowest. For each item, it checks whether the item's label has been used fewer than use_limit times. If there is room, it adds the value to total, increments the label counter, and increments selected. The moment selected reaches num_wanted, the loop breaks early because we have picked enough items.

If the loop finishes without reaching num_wanted, that is fine. We simply return whatever total we have accumulated. This handles cases where there are fewer eligible items than num_wanted.

Visual walkthrough

Let's trace through the example with values = [5,4,3,2,1], labels = [1,1,2,2,3], numWanted = 3, and useLimit = 1.

The algorithm sorts items by value descending, then walks through them one by one. It picks value 5 (label 1), skips value 4 (label 1 is full), picks value 3 (label 2), skips value 2 (label 2 is full), and picks value 1 (label 3). That gives us three selected items with a total of 9.

Complexity analysis

The time complexity is dominated by the sort. The greedy scan is O(n) in the worst case, but sorting costs O(n log n). The space complexity is O(n) for storing the zipped and sorted pairs, plus O(k) for the label counter where k is the number of distinct labels. Since k is at most n, the overall space is O(n).

The building blocks

This problem is built on three reusable patterns that show up across many LeetCode problems.

1. Sort-then-pick pattern

When you need to maximize or minimize a sum under a selection constraint, sorting the candidates by their contribution is usually the first step. After sorting, you iterate and greedily select items that satisfy the constraints.

This same skeleton appears in problems like Assign Cookies (sort cookies and children, then match greedily) and Minimum Number of Arrows to Burst Balloons (sort intervals, then pick greedily). The sorting step is what makes the greedy choice locally optimal at each step.

2. Frequency tracking with a counter

Maintaining a dictionary that counts how many times each label (or category) has been used is a fundamental building block. In this problem, it enforces the useLimit constraint. In other problems, frequency counters appear in sliding window solutions, anagram detection, and task scheduling.

The defaultdict(int) pattern is especially clean because you never need to check whether a key exists before incrementing. Every key starts at zero.

3. Early termination

The if selected == num_wanted: break line is an example of early termination. Once you have collected enough items, there is no reason to continue iterating. This is a small optimization, but it is a good habit. In problems with large inputs, early termination can make a meaningful difference when the answer is found early in the sorted order.

Edge cases

Before submitting, make sure your solution handles these:

• All items share one label: if values = [5,4,3], labels = [1,1,1], numWanted = 3, useLimit = 1, you can only pick one item (value 5). The answer is 5, not 12.
• useLimit is large enough to be irrelevant: if useLimit is greater than or equal to the number of items with any given label, the constraint never triggers. You simply pick the top numWanted items by value.
• numWanted exceeds the number of items: you pick as many as you can. The loop naturally handles this by exhausting all items before reaching numWanted.
• All values are the same: sorting still works. You pick the first numWanted items that fit the label constraints.
• Single item: values = [10], labels = [1], numWanted = 1, useLimit = 1. You pick the only item. Answer is 10.

The greedy solution handles all of these without special-case logic because the sort and counter naturally cover every scenario.

From understanding to recall

You have read through the greedy solution and it makes sense. Sort by value, iterate, check the label counter, pick or skip. Clean and simple. But can you write it from scratch in five minutes without looking at it?

The details matter: using zip to pair values with labels, sorting with reverse=True, using a defaultdict for the counter, checking label_count[label] < use_limit (not <=), and breaking when selected == num_wanted. These are small choices, but getting any one of them wrong produces a buggy solution.

Spaced repetition closes that gap. You practice writing the sort-then-pick loop from scratch at increasing intervals. After a few rounds, the pattern is automatic. You see "maximize sum with per-category limits" and the code flows out without hesitation.

Related posts

• Assign Cookies - Greedy matching with sorted inputs
• Non-overlapping Intervals - Greedy selection under constraints
• Task Scheduler - Frequency-limited scheduling pattern

CodeBricks breaks the Largest Values From Labels problem into its sort-then-pick and frequency-tracking building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a constrained greedy question shows up in your interview, you do not think about it. You just write it.