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.

// 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;
    }
};

Java

  • 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);
                        labelsLimitSet.add(label);
                    } else
                        labelCountMap.put(label, labelCount);
                    sum += value;
                    itemsCount++;
                }
            }
            return sum;
        }
    }
    
  • // 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;
        }
    };
    
  • # 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
            
            
    
    

All Problems

All Solutions