##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1090.html

# 1090. Largest Values From Labels (Medium)

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

Related Topics:
Hash Table, Greedy

## Solution 1.

• class Solution {
public int largestValsFromLabels(int[] values, int[] labels, int num_wanted, int use_limit) {
int length = values.length;
int[][] valuesLabels = new int[length][2];
for (int i = 0; i < length; i++) {
valuesLabels[i][0] = values[i];
valuesLabels[i][1] = labels[i];
}
Arrays.sort(valuesLabels, new Comparator<int[]>() {
public int compare(int[] valueLabel1, int[] valueLabel2) {
if (valueLabel1[0] != valueLabel2[0])
return valueLabel2[0] - valueLabel1[0];
else
return valueLabel1[1] - valueLabel2[1];
}
});
Map<Integer, Integer> labelCountMap = new HashMap<Integer, Integer>();
Set<Integer> labelsLimitSet = new HashSet<Integer>();
int sum = 0;
int itemsCount = 0;
int index = 0;
while (index < length && itemsCount < num_wanted) {
int[] valueLabel = valuesLabels[index++];
int value = valueLabel[0], label = valueLabel[1];
if (!labelsLimitSet.contains(label)) {
int labelCount = labelCountMap.getOrDefault(label, 0);
labelCount++;
if (labelCount == use_limit) {
labelCountMap.remove(label);
} else
labelCountMap.put(label, labelCount);
sum += value;
itemsCount++;
}
}
return sum;
}
}

############

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

• // OJ: https://leetcode.com/problems/largest-values-from-labels/
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
int largestValsFromLabels(vector<int>& values, vector<int>& labels, int num_wanted, int use_limit) {
int N = values.size();
vector<int> id(N);
iota(begin(id), end(id), 0);
sort(begin(id), end(id), [&](int a, int b) { return values[a] > values[b]; });
unordered_map<int, int> m;
int ans = 0;
for (int i = 0; i < N && num_wanted > 0; ++i) {
int j = id[i];
if (m[labels[j]] >= use_limit) continue;
ans += values[j];
m[labels[j]]++;
num_wanted--;
}
return ans;
}
};

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

############

# 1090. Largest Values From Labels
# https://leetcode.com/problems/largest-values-from-labels/

class Solution:
def largestValsFromLabels(self, values: List[int], labels: List[int], num_wanted: int, use_limit: int) -> int:

labels = [i[1] for i in sorted(enumerate(labels), key = lambda x:(-values[x[0]]))]
values.sort(reverse = True)
used = collections.defaultdict(int)

res = i = 0

while i < len(values) and num_wanted > 0:
v, l = values[i], labels[i]

if used[l] < use_limit:
res += v
used[l] += 1
num_wanted -= 1

i += 1

return res


• func largestValsFromLabels(values []int, labels []int, numWanted int, useLimit int) int {
var p [][]int
for i, v := range values {
p = append(p, []int{v, labels[i]})
}
sort.Slice(p, func(i, j int) bool {
return p[i][0] > p[j][0]
})
counter := make(map[int]int)
ans, num := 0, 0
for _, t := range p {
if num >= numWanted {
break
}
v, l := t[0], t[1]
if counter[l] < useLimit {
counter[l]++
num++
ans += v
}
}
return ans
}

• function largestValsFromLabels(
values: number[],
labels: number[],
numWanted: number,
useLimit: number,
): number {
const n = values.length;
const pairs = new Array(n);
for (let i = 0; i < n; ++i) {
pairs[i] = [values[i], labels[i]];
}
pairs.sort((a, b) => b[0] - a[0]);
const cnt: Map<number, number> = new Map();
let ans = 0;
for (let i = 0, num = 0; i < n && num < numWanted; ++i) {
const [v, l] = pairs[i];
if ((cnt.get(l) || 0) < useLimit) {
cnt.set(l, (cnt.get(l) || 0) + 1);
++num;
ans += v;
}
}
return ans;
}