# 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

| Item | Meaning |
|---|---|
| Input | `values`, `labels`, `numWanted`, `useLimit` |
| Output | Maximum sum of chosen items |

Function shape:

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

## Examples

Example 1:

```python
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:

```python
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

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n log n)` | Sorting |
| Space | `O(n)` | Label count map |

## 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

```python
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

```python
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()
```

| Test | Expected | Why |
|---|---:|---|
| `useLimit=1` | `9` | One per label, pick top 3 |
| `useLimit=2` | `12` | Two from label 3 allowed |
| Multiple same label | `16` | Only one from label 0, best two total |