> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/greedy/largest-values-from-labels.md).

# Largest Values From Labels

We have a set of items: the `i`-th item has value `values[i]` and label `labels[i]`.

Then, we choose a subset `S` of these items, such that:

* `|S| <= num_wanted`
* For every label `L`, the number of items in `S` with label `L` is `<= use_limit`.

Return the largest possible sum of the subset `S`.

**Example 1:**

```
Input: values = [5,4,3,2,1], labels = [1,1,2,2,3], num_wanted = 3, use_limit = 1
Output: 9
Explanation: The subset chosen is the first, third, and fifth item.
```

**Example 2:**

```
Input: values = [5,4,3,2,1], labels = [1,3,3,3,2], num_wanted = 3, use_limit = 2
Output: 12
Explanation: The subset chosen is the first, second, and third item.
```

**Example 3:**

```
Input: values = [9,8,8,7,6], labels = [0,0,0,1,1], num_wanted = 3, use_limit = 1
Output: 16
Explanation: The subset chosen is the first and fourth item.
```

**Example 4:**

```
Input: values = [9,8,8,7,6], labels = [0,0,0,1,1], num_wanted = 3, use_limit = 2
Output: 24
Explanation: The subset chosen is the first, second, and fourth item.
```

**Note:**

1. `1 <= values.length == labels.length <= 20000`
2. `0 <= values[i], labels[i] <= 20000`
3. `1 <= num_wanted, use_limit <= values.length`

```java
class Solution {
    public int largestValsFromLabels(int[] values, int[] labels, int num_wanted, int use_limit) {
        int[][] nums = new int[values.length][2];
        for (int i = 0; i < values.length; i++) {
            nums[i][0] = values[i];
            nums[i][1] = labels[i];
        }
        Arrays.sort(nums, (a, b) -> b[0] - a[0]);
        int sum = 0;
        HashMap<Integer, Integer> limit = new HashMap<>();
        for (int label : labels)
            limit.put(label, 0);
        for (int i = 0; i < nums.length; i++) {
            if (limit.get(nums[i][1]) < use_limit) {
                limit.put(nums[i][1], limit.get(nums[i][1]) + 1);
                num_wanted--;
                sum += nums[i][0];
            }
            if (num_wanted == 0)
                break;
        }
        return sum;
    }
}
```