# Largest Values From Labels
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/largest-values-from-labels)
Canonical: https://scaleengineer.com/dsa/problems/largest-values-from-labels
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table
---
## Problem
You are given `n` item's value and label as two integer arrays `values` and `labels`. You are also given two integers `numWanted` and `useLimit`.

Your task is to find a subset of items with the **maximum sum** of their values such that:

* The number of items is **at most** `numWanted`.
* The number of items with the same label is **at most** `useLimit`.

Return the maximum sum.

**Example 1:**

**Input:** values = \[5,4,3,2,1\], labels = \[1,1,2,2,3\], numWanted = 3, useLimit = 1

**Output:** 9

**Explanation:**

The subset chosen is the first, third, and fifth items with the sum of values 5 + 3 + 1.

**Example 2:**

**Input:** values = \[5,4,3,2,1\], labels = \[1,3,3,3,2\], numWanted = 3, useLimit = 2

**Output:** 12

**Explanation:**

The subset chosen is the first, second, and third items with the sum of values 5 + 4 + 3.

**Example 3:**

**Input:** values = \[9,8,8,7,6\], labels = \[0,0,0,1,1\], numWanted = 3, useLimit = 1

**Output:** 16

**Explanation:**

The subset chosen is the first and fourth items with the sum of values 9 + 7.

**Constraints:**

* `n == values.length == labels.length`
* `1 <= n <= 2 * 104`
* `0 <= values[i], labels[i] <= 2 * 104`
* `1 <= numWanted, useLimit <= n`

# Approaches
## Brute Force by Generating All Subsets
This approach explores every possible subset of items. For each subset, it checks if it adheres to the given constraints: the total number of items is no more than `numWanted`, and the count for each label does not exceed `useLimit`. If a subset is valid, its total value is calculated. The algorithm maintains a variable to store the maximum sum found across all valid subsets.
**Time:** O(2^n * n). There are `2^n` possible subsets. For each subset, we iterate through its elements (up to `n` in length) to check validity and calculate the sum. This is computationally prohibitive for the given constraints. · **Space:** O(n). The space is needed for the recursion stack and to store the current subset being processed, along with a hash map for label counts.
**Pros:** Guaranteed to find the correct answer by exploring all possibilities.
**Cons:** Extremely slow and will result in a 'Time Limit Exceeded' error for the given constraints.
### Explanation
The brute-force method systematically generates every single combination of items. For each combination, it performs two checks: first, whether the size of the subset is within the `numWanted` limit, and second, whether the usage of any single label is within the `useLimit`. This is done by counting the items and their labels for each subset. If a subset is deemed valid, its total value is computed and compared against the maximum sum found so far, updating it if necessary. While this method is guaranteed to find the optimal solution, its exponential nature makes it impractical for anything but very small inputs.

```java
// This is a conceptual illustration. A full implementation would be too complex and inefficient.
class Solution {
    int maxSum = 0;

    public int largestValsFromLabels(int[] values, int[] labels, int numWanted, int useLimit) {
        // A recursive helper function would generate all subsets.
        // findSubsets(0, new ArrayList<>(), values, labels, numWanted, useLimit);
        // return maxSum;
        // Due to the 2^n complexity, this approach is not feasible and is omitted.
        return -1; // Placeholder for an infeasible solution
    }

    // void findSubsets(int index, List<Integer> currentSubsetIndices, ...) {
    //     // Base case: if index reaches the end
    //     if (index == values.length) {
    //         // Check if current subset is valid
    //         // If valid, calculate sum and update maxSum
    //         return;
    //     }
    //     // Recurse without including the current item
    //     findSubsets(index + 1, currentSubsetIndices, ...);
    //     // Recurse including the current item
    //     currentSubsetIndices.add(index);
    //     findSubsets(index + 1, currentSubsetIndices, ...);
    //     currentSubsetIndices.remove(currentSubsetIndices.size() - 1);
    // }
}
```
### Algorithm
- Use a recursive or iterative method to generate all `2^n` subsets of the `n` items.
- For each generated subset:
    - Verify its validity:
        - Check if the number of items in the subset is at most `numWanted`.
        - Use a hash map to count the occurrences of each label in the subset. Check if any label count exceeds `useLimit`.
    - If the subset is valid, calculate the sum of its values.
    - Update the overall maximum sum if the current subset's sum is greater.
- Return the overall maximum sum after checking all subsets.

## Greedy Approach with Sorting
The problem asks for the maximum sum, which suggests a greedy strategy. The most intuitive greedy choice is to always pick the available item with the highest value. To implement this, we can pair up the values and labels, sort them in descending order based on the values, and then iterate through them. We pick an item if it doesn't violate the constraints on the total number of items (`numWanted`) and the per-label usage (`useLimit`).
**Time:** O(n log n). Creating the list of items takes `O(n)`. Sorting the list dominates the complexity, taking `O(n log n)`. The final iteration through the sorted list takes `O(n)`. · **Space:** O(n). We need `O(n)` space to store the list of `Item` objects. The hash map for label counts can also store up to `n` unique labels in the worst case, taking `O(n)` space.
**Pros:** Much more efficient than brute force and guaranteed to be correct for this problem.; Relatively simple to understand and implement.
**Cons:** The O(n log n) sorting step is slightly less efficient than a linear-time solution.
### Explanation
This approach relies on the greedy principle that to maximize a sum, one should always prioritize adding the largest available numbers. 

First, we combine the `values` and `labels` arrays into a single structure, like a list of `Item` objects, to keep them paired. Then, we sort these items based on their value in descending order. This ensures that we process items from most valuable to least valuable.

We then iterate through this sorted list. For each item, we check if we can select it. A selection is valid if we haven't yet reached our quota of `numWanted` items and if the number of items already chosen with the same label is less than `useLimit`. We use a hash map to keep track of the counts of each label selected so far. If the item can be selected, we add its value to our total sum and update our counts. We continue this process until we have either considered all items or have selected `numWanted` items.

```java
class Item {
    int value;
    int label;
    Item(int value, int label) {
        this.value = value;
        this.label = label;
    }
}

class Solution {
    public int largestValsFromLabels(int[] values, int[] labels, int numWanted, int useLimit) {
        int n = values.length;
        List<Item> items = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            items.add(new Item(values[i], labels[i]));
        }

        // Sort items by value in descending order
        items.sort((a, b) -> b.value - a.value);

        Map<Integer, Integer> labelCounts = new HashMap<>();
        int maxSum = 0;
        int itemsChosen = 0;

        for (Item item : items) {
            if (itemsChosen == numWanted) {
                break;
            }

            int currentLabelCount = labelCounts.getOrDefault(item.label, 0);
            if (currentLabelCount < useLimit) {
                maxSum += item.value;
                itemsChosen++;
                labelCounts.put(item.label, currentLabelCount + 1);
            }
        }

        return maxSum;
    }
}
```
### Algorithm
- Create a list of custom objects or pairs, where each object holds an item's value and its label.
- Sort this list of items in descending order based on their values.
- Initialize `maxSum = 0`, `itemsChosen = 0`, and a hash map `labelCounts` to track the usage of each label.
- Iterate through the sorted list of items.
- For each item, if adding it does not violate the `numWanted` and `useLimit` constraints, add its value to `maxSum`, increment `itemsChosen`, and update its label's count in the map.
- Stop early if `itemsChosen` reaches `numWanted`.
- Return `maxSum`.

## Optimized Greedy Approach using Bucketing
This approach is an optimization of the standard greedy method. Instead of a general-purpose comparison sort (`O(n log n)`), we can use a non-comparison sorting technique like counting sort or bucketing. This is possible because the item values are non-negative integers within a known, limited range. This allows us to effectively sort the items and process them in descending order of value in linear time.
**Time:** O(n + V_max). Populating the buckets takes `O(n)`. Iterating through the buckets takes `O(V_max)` for the outer loop, and the inner loops over all buckets will execute a total of `n` times across all iterations. Thus, the total time is linear. · **Space:** O(n + V_max), where `n` is the number of items and `V_max` is the maximum possible value. The `buckets` array requires `O(V_max)` for the array itself plus `O(n)` to store all the labels. The `labelCounts` map can take up to `O(n)` space.
**Pros:** Achieves optimal linear time complexity.; Very efficient for the given problem constraints.
**Cons:** Uses more space than the comparison-sort approach if the maximum value `V_max` is significantly larger than `n`. For this problem's constraints, they are of similar magnitude.
### Explanation
The core of this optimized greedy approach is to avoid a comparison-based sort. Since item values are bounded, we can use an array as a set of 'buckets' to group items by value. The index of the array represents a value, and the element at that index is a list of labels of all items having that value.

1.  We create an array of lists, `buckets`, where the size is determined by the maximum possible value (20001 according to constraints).
2.  We iterate through the input items once, placing each item's label into the corresponding value's bucket. For example, an item with `value=50, label=1` results in `1` being added to `buckets[50]`.
3.  After populating the buckets, we iterate through the `buckets` array from the highest index (highest value) down to zero. This naturally processes items in descending order of value.
4.  For each value, we look at the labels in its bucket. For each label, we apply the same greedy logic as before: if we have room for more items (`itemsChosen < numWanted`) and haven't exhausted the limit for that label (`labelCounts.get(...) < useLimit`), we select the item. 
5.  This continues until we have selected `numWanted` items or have checked all buckets.

This method achieves a linear time complexity because it avoids the `O(n log n)` sorting step.

```java
class Solution {
    public int largestValsFromLabels(int[] values, int[] labels, int numWanted, int useLimit) {
        // The maximum value is constrained to 20000
        int maxVal = 20001;
        List<Integer>[] buckets = new ArrayList[maxVal];
        for (int i = 0; i < maxVal; i++) {
            buckets[i] = new ArrayList<>();
        }

        for (int i = 0; i < values.length; i++) {
            buckets[values[i]].add(labels[i]);
        }

        Map<Integer, Integer> labelCounts = new HashMap<>();
        int maxSum = 0;
        int itemsChosen = 0;

        for (int v = maxVal - 1; v >= 0; v--) {
            if (itemsChosen == numWanted) {
                break;
            }
            if (buckets[v].isEmpty()) {
                continue;
            }

            for (int label : buckets[v]) {
                if (itemsChosen == numWanted) {
                    break;
                }
                int currentLabelCount = labelCounts.getOrDefault(label, 0);
                if (currentLabelCount < useLimit) {
                    maxSum += v;
                    itemsChosen++;
                    labelCounts.put(label, currentLabelCount + 1);
                }
            }
        }
        return maxSum;
    }
}
```
### Algorithm
- Determine the maximum possible value `maxVal` from the constraints.
- Create an array of lists (buckets) of size `maxVal + 1`.
- Populate the buckets: for each item `(values[i], labels[i])`, add `labels[i]` to the list at `buckets[values[i]]`.
- Initialize `maxSum = 0`, `itemsChosen = 0`, and a hash map `labelCounts`.
- Iterate downwards from `v = maxVal - 1` to `0`.
- For each value `v`, iterate through the labels in `buckets[v]`.
- For each label, check if adding the item is valid (respects `numWanted` and `useLimit`).
- If valid, add `v` to `maxSum`, increment `itemsChosen`, and update the label count.
- Stop if `itemsChosen` reaches `numWanted`.
- Return `maxSum`.

# Solutions
### Java

```java
class Solution {
public
  int largestValsFromLabels(int[] values, int[] labels, int numWanted,
                            int useLimit) {
    int n = values.length;
    int[][] pairs = new int[n][2];
    for (int i = 0; i < n; ++i) {
      pairs[i] = new int[]{values[i], labels[i]};
    }
    Arrays.sort(pairs, (a, b)->b[0] - a[0]);
    Map<Integer, Integer> cnt = new HashMap<>();
    int ans = 0, num = 0;
    for (int i = 0; i < n && num < numWanted; ++i) {
      int v = pairs[i][0], l = pairs[i][1];
      if (cnt.getOrDefault(l, 0) < useLimit) {
        cnt.merge(l, 1, Integer : : sum);
        num += 1;
        ans += v;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int largestValsFromLabels(vector<int> &values, vector<int> &labels,
                            int numWanted, int useLimit) {
    int n = values.size();
    vector<pair<int, int>> pairs(n);
    for (int i = 0; i < n; ++i) {
      pairs[i] = {-values[i], labels[i]};
    }
    sort(pairs.begin(), pairs.end());
    unordered_map<int, int> cnt;
    int ans = 0, num = 0;
    for (int i = 0; i < n && num < numWanted; ++i) {
      int v = -pairs[i].first, l = pairs[i].second;
      if (cnt[l] < useLimit) {
        ++cnt[l];
        ++num;
        ans += v;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int: ans = num = 0 cnt = Counter() for v, l in sorted(zip(values, labels), reverse=True): if cnt[l] < useLimit: cnt[l] += 1 num += 1 ans += v if num == numWanted: break return ans

```