Code Implementation

class Solution:
    def largestValsFromLabels(self, values, labels, num_wanted, use_limit):
        items = sorted(zip(values, labels), reverse=True)
        label_count = {}
        total = 0
        count = 0
        for value, label in items:
            if label_count.get(label, 0) < use_limit:
                total += value
                label_count[label] = label_count.get(label, 0) + 1
                count += 1
                if count == num_wanted:
                    break
        return total
      

class Solution {
public:
    int largestValsFromLabels(vector<int>& values, vector<int>& labels, int num_wanted, int use_limit) {
        vector<pair<int, int>> items;
        for (int i = 0; i < values.size(); ++i)
            items.push_back({values[i], labels[i]});
        sort(items.rbegin(), items.rend());
        unordered_map<int, int> label_count;
        int total = 0, count = 0;
        for (auto& item : items) {
            int value = item.first, label = item.second;
            if (label_count[label] < use_limit) {
                total += value;
                label_count[label]++;
                count++;
                if (count == num_wanted)
                    break;
            }
        }
        return total;
    }
};
      

class Solution {
    public int largestValsFromLabels(int[] values, int[] labels, int num_wanted, int use_limit) {
        int n = values.length;
        int[][] items = new int[n][2];
        for (int i = 0; i < n; ++i) {
            items[i][0] = values[i];
            items[i][1] = labels[i];
        }
        Arrays.sort(items, (a, b) -> b[0] - a[0]);
        Map<Integer, Integer> labelCount = new HashMap<>();
        int total = 0, count = 0;
        for (int[] item : items) {
            int value = item[0], label = item[1];
            if (labelCount.getOrDefault(label, 0) < use_limit) {
                total += value;
                labelCount.put(label, labelCount.getOrDefault(label, 0) + 1);
                count++;
                if (count == num_wanted)
                    break;
            }
        }
        return total;
    }
}
      

var largestValsFromLabels = function(values, labels, num_wanted, use_limit) {
    let items = [];
    for (let i = 0; i < values.length; ++i) {
        items.push([values[i], labels[i]]);
    }
    items.sort((a, b) => b[0] - a[0]);
    let labelCount = new Map();
    let total = 0, count = 0;
    for (let [value, label] of items) {
        if ((labelCount.get(label) || 0) < use_limit) {
            total += value;
            labelCount.set(label, (labelCount.get(label) || 0) + 1);
            count++;
            if (count === num_wanted)
                break;
        }
    }
    return total;
};
      

Problem Description

You are given two lists of integers, values and labels, both of the same length. Each values[i] is associated with the label labels[i]. You are also given two integers: num_wanted (the maximum number of elements you can select) and use_limit (the maximum number of elements you can select with the same label).

The goal is to pick at most num_wanted elements from values, such that:

• No label is used more than use_limit times.
• The sum of the selected values is maximized.

Thought Process

At first glance, the problem seems to ask for the largest possible sum from a subset of values, with the twist that you can't pick too many values with the same label. A brute-force approach would be to check all possible subsets of values of size at most num_wanted, but this quickly becomes infeasible as the input size grows.

Instead, we notice that to maximize the sum, we want to pick the largest values first, but only if we haven't already used up the allowed number of that label. This suggests a greedy approach: sort all items by value (descending), and pick them one by one, keeping track of how many times we've used each label.

This approach is not only simpler but much more efficient than brute force, as it avoids generating all subsets and instead makes only a single pass through the sorted values.

Solution Approach

• Step 1: Pair each value with its corresponding label, creating a list of (value, label) pairs.
• Step 2: Sort these pairs in descending order by value. This ensures we always consider the largest available value first.
• Step 3: Initialize a counter (such as a hash map) to keep track of how many times we've used each label.
• Step 4: Iterate through the sorted list:
  • If we haven't yet picked num_wanted elements, and the current label hasn't reached its use_limit, select this value.
  • Increment the label's count and the total selected count.
  • Stop when we've picked num_wanted elements.
• Step 5: Return the sum of the selected values.

We use a hash map (dictionary) for label counts because it provides O(1) lookups and updates, making the entire process efficient.

Example Walkthrough

Suppose values = [5,4,3,2,1], labels = [1,1,2,2,3], num_wanted = 3, use_limit = 1.

1. Pair and sort: [(5,1), (4,1), (3,2), (2,2), (1,3)] (already sorted).
2. Initialize label_count = {}, count = 0, total = 0.
3. First item (5,1): label 1 used 0 times, which is < 1. Pick it. label_count = {1:1}, total = 5, count = 1.
4. Second item (4,1): label 1 used 1 time, which is not < 1. Skip.
5. Third item (3,2): label 2 used 0 times. Pick it. label_count = {1:1, 2:1}, total = 8, count = 2.
6. Fourth item (2,2): label 2 used 1 time. Skip.
7. Fifth item (1,3): label 3 used 0 times. Pick it. label_count = {1:1, 2:1, 3:1}, total = 9, count = 3.
8. Picked 3 elements, done. Return 9.

At each step, we only pick a value if it doesn't exceed the label's limit and we still have room left to select more.

Time and Space Complexity

Brute-force Approach: Checking all possible subsets of up to num_wanted elements is exponential in time, specifically O(2^n), which is infeasible for large n.

Optimized Greedy Approach:

• Time Complexity: Sorting the pairs takes O(n log n). Iterating through the sorted list is O(n). So, total time is O(n log n).
• Space Complexity: We use O(n) space to store the pairs and O(k) space for the label counter, where k is the number of unique labels. So, overall space is O(n).

Summary

The key insight is to always pick the largest available value, but only if its label hasn't reached the use_limit. By sorting all (value, label) pairs and greedily selecting valid options, we maximize the sum efficiently. Using a hash map for label counts ensures fast lookups and updates. This approach is both simple and optimal for this problem, demonstrating the power of greedy algorithms when constraints are local and can be checked incrementally.