1090. Largest Values From Labels

MediumGreedyArrayHash TableCountingSorting
Leetcode Link

Problem Description

In this problem, there is a set of n items, each with an associated value and label. Two arrays values and labels represent these, where values[i] is the value and labels[i] is the label for the i-th item. We are given two additional integers, numWanted which represents the maximum number of items to choose, and useLimit which represents the maximum number of items with the same label we are allowed to choose.

The goal is to find a subset s of these items that maximizes the total value (or "score") while adhering to the constraints:

  1. The size of s is less than or equal to numWanted.
  2. No more than useLimit items in s can have the same label.

The desired output is the maximum score that can be achieved following these rules.

Intuition

The intuitive approach to solving this problem is to maximize the value while respecting the constraints given. To start, since we want the maximum value, we should consider the items with the highest values first. Hence, we sort the items by value in descending order. Once sorted, a simple strategy can be employed:

  • Iterate over the list of items in order of descending value.
  • Keep a count of how many items with each label have been added to our subset s.
  • Add the value of the current item to our score if the count of items with the same label is less than the useLimit.
  • Increment the count of items chosen.
  • If the number of items chosen reaches numWanted, we've found the best possible subset, and we can stop and return the score.

This approach ensures that we are always adding the item with the highest available value while respecting the useLimit condition for labels and not exceeding the desired subset size numWanted.

Solution Approach

The solution approach relies on a greedy algorithm that selects items with higher values first, while ensuring that it does not select more than useLimit items with the same label. To accomplish this effectively, the following steps are taken:

  • Sorting: We need to sort the items by their values in descending order. To do so, we use Python's built-in sorted function, pairing each value with its corresponding label using zip(values, labels). The reverse=True parameter is used to sort the pairs in descending order of value.

  • Counting: To keep track of the number of items with the same label selected, we use a Counter from Python's collections module. This data structure allows easy increments and tracking of counts corresponding to each label.

  • Selection Loop: Iterate through the sorted pairs of (value, label). For each pair, check if the current label's count is less than the useLimit using the previously initialized Counter.

  • If the label's count is within the limit, we proceed to include the item's value in our current subset score ans and increment the count for that label in the Counter.

  • We also keep a tally of the total number of items selected in num. When num reaches numWanted, we have selected the maximum allowed number of items, and we break out of the loop since we cannot add any more items to the subset.

  • Finally, after the loop (either once we've reached numWanted or gone through all items), we return ans as the maximum score obtained from the selected subset of items.

The combination of sorting, counting, and a selection loop makes this greedy algorithm efficient and ensures that at each step, the best choice is made towards achieving the optimal solution (maximizing the subset score under the given constraints).

Mathematically, if we denote v as the value and l as the label of the current item being considered, and cnt as the Counter for labels, the pseudo-code can be described as follows:

1sort items by value in descending order
2initialize ans to 0, num to 0, and cnt to Counter()
3for each (v, l) in sorted items:
4    if cnt[l] < useLimit:
5        cnt[l] += 1
6        num += 1
7        ans += v
8        if num == numWanted:
9            break
10return ans

This implementation ensures that our greedy algorithm selects items in a way that maximizes the score while conforming to the constraints of numWanted and useLimit.

💪
Level Up Your
Algo Skills

Example Walkthrough

Consider the following small example to illustrate the solution approach:

Suppose we have the following input:

  • values = [5, 4, 3, 2, 1]
  • labels = [1, 1, 2, 2, 3]
  • numWanted = 3
  • useLimit = 1

Following the solution approach, we would execute these steps:

  1. Sort the items by value in descending order:

    We pair each value with its corresponding label and sort:

    Before sorting:

    • values: [5, 4, 3, 2, 1]
    • labels: [1, 1, 2, 2, 3]

    After sorting:

    • sorted_pairs: [(5, 1), (4, 1), (3, 2), (2, 2), (1, 3)]
  2. Initialize the counter and other variables:

    We start with an empty Counter to track the labels, ans as 0 (our cumulative value), and num as 0 (the number of items in our subset):

    • ans (max score): 0
    • num (number of items selected): 0
    • cnt (the Counter for labels): {}
  3. Selection Loop:

    We iterate over the sorted pairs and apply the constraints:

    a) (5, 1): Count for label 1 is 0, which is less than useLimit. We select this item.

    • ans becomes 5 (0 + 5)
    • num becomes 1 (0 + 1)
    • cnt becomes {1: 1}

    b) (4, 1): Count for label 1 is currently 1, equal to useLimit. We cannot select this item.

    c) (3, 2): Count for label 2 is 0, which is less than useLimit. We select this item.

    • ans becomes 8 (5 + 3)
    • num becomes 2 (1 + 1)
    • cnt becomes {1: 1, 2: 1}

    d) (2, 2): Count for label 2 is currently 1, equal to useLimit. We cannot select this item.

    e) (1, 3): Count for label 3 is 0, which is less than useLimit. We select this item.

    • ans becomes 9 (8 + 1)
    • num becomes 3 (2 + 1) --> This reaches numWanted, we stop selecting items.
    • cnt becomes {1: 1, 2: 1, 3: 1}
  4. Return the maximum score:

    Since we have selected the maximum number of items (numWanted), we return ans which is 9. This is the maximum score we can achieve by selecting a subset of 3 items following the given constraints.

    The selected subset is represented by the pairs (5, 1), (3, 2), and (1, 3), leading to the maximum value of 9.

Applying this approach has allowed us to maximize our score under the constraints of numWanted and useLimit.

Python Solution

1from collections import Counter
2from typing import List
3
4class Solution:
5    def largestValsFromLabels(self, values: List[int], labels: List[int], num_wanted: int, use_limit: int) -> int:
6        # Initialize the answer variable to store the sum of the largest values
7        # and a count variable to keep track of how many values are included
8        total_value = 0
9        chosen_count = 0
10      
11        # Create a counter to keep track of how many times each label has been used
12        label_count = Counter()
13      
14        # Sort the value-label pairs in decreasing order of values to pick the largest values first
15        for value, label in sorted(zip(values, labels), reverse=True):
16            # Check if the current label has been used less than the use_limit
17            if label_count[label] < use_limit:
18                # If so, increment the count for the label
19                label_count[label] += 1
20                # Increment the count of chosen values
21                chosen_count += 1
22                # Add the current value to the total_value
23                total_value += value
24                # If we have reached the num_wanted, no need to consider further values
25                if chosen_count == num_wanted:
26                    break
27      
28        # Return the final sum of the chosen values
29        return total_value
30

Java Solution

1import java.util.Arrays;
2import java.util.HashMap;
3import java.util.Map;
4
5class Solution {
6    public int largestValsFromLabels(int[] values, int[] labels, int numWanted, int useLimit) {
7        int itemCount = values.length; // Total number of items
8        int[][] valueLabelPairs = new int[itemCount][2]; // To store value-label pairs
9      
10        // Populate the value-label pairs for sorting
11        for (int i = 0; i < itemCount; ++i) {
12            valueLabelPairs[i] = new int[] {values[i], labels[i]};
13        }
14      
15        // Sort the pairs in descending order based on the values
16        Arrays.sort(valueLabelPairs, (pair1, pair2) -> pair2[0] - pair1[0]);
17      
18        Map<Integer, Integer> labelUsageCount = new HashMap<>(); // Map to keep track of label usage
19      
20        int totalValue = 0; // Sum of values selected
21        int itemsSelected = 0; // Number of items selected
22      
23        // Iterate over sorted value-label pairs
24        for (int i = 0; i < itemCount && itemsSelected < numWanted; ++i) {
25            int currentValue = valueLabelPairs[i][0]; // Current item's value
26            int currentLabel = valueLabelPairs[i][1]; // Current item's label
27          
28            // Check if we can use more items with this label
29            if (labelUsageCount.getOrDefault(currentLabel, 0) < useLimit) {
30                // If yes, select the current item
31                labelUsageCount.merge(currentLabel, 1, Integer::sum); // Increment label usage
32                itemsSelected++; // Increment number of selected items
33                totalValue += currentValue; // Add value to total
34            }
35        }
36      
37        return totalValue; // Return the sum of the selected values
38    }
39}
40

C++ Solution

1#include <vector>
2#include <unordered_map>
3#include <algorithm>
4using namespace std;
5
6class Solution {
7public:
8    int largestValsFromLabels(vector<int>& values, vector<int>& labels, int numWanted, int useLimit) {
9        int itemCount = values.size(); // Item count from the given values.
10        vector<pair<int, int>> valueLabelPairs(itemCount);
11
12        // Pairing values with labels and negating values for reverse sort.
13        for (int i = 0; i < itemCount; ++i) {
14            valueLabelPairs[i] = {-values[i], labels[i]};
15        }
16
17        // Sort pairs by value in descending order.
18        sort(valueLabelPairs.begin(), valueLabelPairs.end());
19      
20        unordered_map<int, int> labelCount; // To track the number of times a label has been used.
21        int totalValue = 0; // Total value of selected items.
22        int selectedItems = 0; // Number of items selected.
23
24        // Iterate over the sorted pairs.
25        for (int i = 0; i < itemCount && selectedItems < numWanted; ++i) {
26            int value = -valueLabelPairs[i].first; // Reverse negation to get the original value.
27            int label = valueLabelPairs[i].second;
28
29            // Check if we can use more items with this label.
30            if (labelCount[label] < useLimit) {
31                labelCount[label]++; // Increment the use count of this label.
32                selectedItems++; // One more item is selected.
33                totalValue += value; // Increase the total value by this item's value.
34            }
35        }
36
37        return totalValue; // Return the total value of the selected items.
38    }
39};
40

Typescript Solution

1function largestValsFromLabels(
2    values: number[],
3    labels: number[],
4    numWanted: number,
5    useLimit: number,
6): number {
7    // The number of items in the values array
8    const itemCount = values.length;
9
10    // Combine each value with its corresponding label into a pair
11    const valueLabelPairs = new Array(itemCount);
12    for (let i = 0; i < itemCount; ++i) {
13        valueLabelPairs[i] = [values[i], labels[i]];
14    }
15
16    // Sort the pairs descending by value
17    valueLabelPairs.sort((a, b) => b[0] - a[0]);
18
19    // Initialize a map to keep count of used labels
20    const labelCount: Map<number, number> = new Map();
21
22    // Initialize the accumulator for the sum of the largest values
23    let totalValue = 0;
24
25    // Loop through the sorted pairs, and pick the largest unused values
26    // respecting the useLimit for labels. We also respect the numWanted limit.
27    for (let i = 0, chosenItems = 0; i < itemCount && chosenItems < numWanted; ++i) {
28        const [value, label] = valueLabelPairs[i];
29        // Retrieve the current count for this label, defaulting to 0 if not present
30        const currentCount = labelCount.get(label) || 0;
31
32        // If we haven't reached the useLimit for this label, choose this value
33        if (currentCount < useLimit) {
34            labelCount.set(label, currentCount + 1); // Increment the count for this label
35            chosenItems++; // Increment the count of chosen items
36            totalValue += value; // Add the value to the total
37        }
38    }
39
40    // Return the sum of the largest values chosen
41    return totalValue;
42}
43

Time and Space Complexity

The given Python code snippet is a function that selects the largest values from a list values, each associated with a label from the list labels, with two constraints: a maximum number of items selected (numWanted) and a maximum number of times each label can be used (useLimit). The function returns the sum of the largest values selected according to these constraints.

Time Complexity

The time complexity of the code can be broken down as follows:

  1. Sorting the combined list of values and labels: sorted(zip(values, labels), reverse=True) takes O(N log N) time, where N is the length of the values (and labels) list.

  2. The for loop iterates over the sorted list, which has N elements. In the worst case, it will iterate over all N elements once.

  3. Inside the loop, updating the Counter and performing basic arithmetic operations are O(1) operations.

Combining these operations, the overall time complexity of the code is dominated by the sorting step, resulting in O(N log N).

Space Complexity

The space complexity can be analyzed as follows:

  1. The additional space used by the sorted list of zipped values and labels is O(N), where N is the length of the original lists.

  2. The Counter object cnt which keeps track of the number of times each label has been used will, in the worst case, have as many elements as there are distinct labels. In the worst case, this can also be O(N) if every value has a unique label.

Therefore, the overall space complexity is O(N) due to the space required to store the sorted list and the counter.

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫