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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


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

1
2
3
4
5
6
7
8
9


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 * 10^4
  • 0 <= values[i], labels[i] <= 2 * 10^4
  • 1 <= numWanted, useLimit <= n

Solution

Method 1 – Greedy with Sorting and Counting

Intuition

To maximize the sum, always pick the largest available value, but do not exceed the useLimit for any label and do not pick more than numWanted items. Sorting by value allows us to greedily select the best items.

Approach

  1. Pair each value with its label and sort all pairs in descending order by value.
  2. Use a hash map to count how many times each label has been used.
  3. Iterate through the sorted pairs:
    • If the label’s count is less than useLimit and we have not picked numWanted items, add the value to the answer and increment the label’s count.
    • Stop when numWanted items have been picked.
  4. Return the total sum.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int largestValsFromLabels(vector<int>& values, vector<int>& labels, int numWanted, int useLimit) {
        vector<pair<int, int>> items;
        for (int i = 0; i < values.size(); ++i) items.emplace_back(values[i], labels[i]);
        sort(items.rbegin(), items.rend());
        unordered_map<int, int> cnt;
        int ans = 0, used = 0;
        for (auto& [v, l] : items) {
            if (cnt[l] < useLimit) {
                ans += v;
                cnt[l]++;
                used++;
                if (used == numWanted) break;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

func largestValsFromLabels(values []int, labels []int, numWanted int, useLimit int) int {
    n := len(values)
    items := make([][2]int, n)
    for i := 0; i < n; i++ { items[i] = [2]int{values[i], labels[i]} }
    sort.Slice(items, func(i, j int) bool { return items[i][0] > items[j][0] })
    cnt := map[int]int{}
    ans, used := 0, 0
    for _, it := range items {
        v, l := it[0], it[1]
        if cnt[l] < useLimit {
            ans += v
            cnt[l]++
            used++
            if used == numWanted { break }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int largestValsFromLabels(int[] values, int[] labels, int numWanted, int useLimit) {
        int n = values.length;
        int[][] items = new int[n][2];
        for (int i = 0; i < n; ++i) items[i] = new int[]{values[i], labels[i]};
        Arrays.sort(items, (a, b) -> b[0] - a[0]);
        Map<Integer, Integer> cnt = new HashMap<>();
        int ans = 0, used = 0;
        for (int[] it : items) {
            int v = it[0], l = it[1];
            if (cnt.getOrDefault(l, 0) < useLimit) {
                ans += v;
                cnt.put(l, cnt.getOrDefault(l, 0) + 1);
                used++;
                if (used == numWanted) break;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    fun largestValsFromLabels(values: IntArray, labels: IntArray, numWanted: Int, useLimit: Int): Int {
        val items = values.indices.map { values[it] to labels[it] }.sortedByDescending { it.first }
        val cnt = mutableMapOf<Int, Int>()
        var ans = 0
        var used = 0
        for ((v, l) in items) {
            if ((cnt[l] ?: 0) < useLimit) {
                ans += v
                cnt[l] = (cnt[l] ?: 0) + 1
                used++
                if (used == numWanted) break
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def largestValsFromLabels(self, values: list[int], labels: list[int], numWanted: int, useLimit: int) -> int:
        items = sorted(zip(values, labels), reverse=True)
        cnt = {}
        ans = used = 0
        for v, l in items:
            if cnt.get(l, 0) < useLimit:
                ans += v
                cnt[l] = cnt.get(l, 0) + 1
                used += 1
                if used == numWanted:
                    break
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

use std::collections::HashMap;
impl Solution {
    pub fn largest_vals_from_labels(values: Vec<i32>, labels: Vec<i32>, num_wanted: i32, use_limit: i32) -> i32 {
        let mut items: Vec<(i32, i32)> = values.into_iter().zip(labels.into_iter()).collect();
        items.sort_by(|a, b| b.0.cmp(&a.0));
        let mut cnt = HashMap::new();
        let mut ans = 0;
        let mut used = 0;
        for (v, l) in items {
            let c = cnt.entry(l).or_insert(0);
            if *c < use_limit {
                ans += v;
                *c += 1;
                used += 1;
                if used == num_wanted { break; }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    largestValsFromLabels(values: number[], labels: number[], numWanted: number, useLimit: number): number {
        const items = values.map((v, i) => [v, labels[i]]).sort((a, b) => b[0] - a[0])
        const cnt = new Map<number, number>()
        let ans = 0, used = 0
        for (const [v, l] of items) {
            if ((cnt.get(l) ?? 0) < useLimit) {
                ans += v
                cnt.set(l, (cnt.get(l) ?? 0) + 1)
                used++
                if (used === numWanted) break
            }
        }
        return ans
    }
}

Complexity

  • ⏰ Time complexity: O(n log n), where n is the number of items. Sorting dominates.
  • 🧺 Space complexity: O(n), for storing and counting items.