1090. Largest Values From Labels
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:
- The size of
s
is less than or equal tonumWanted
. - No more than
useLimit
items ins
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 usingzip(values, labels)
. Thereverse=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'scollections
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 theuseLimit
using the previously initializedCounter
. -
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 theCounter
. -
We also keep a tally of the total number of items selected in
num
. Whennum
reachesnumWanted
, 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 returnans
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
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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
= 3useLimit
= 1
Following the solution approach, we would execute these steps:
-
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)]
-
Initialize the counter and other variables:
We start with an empty
Counter
to track the labels,ans
as 0 (our cumulative value), andnum
as 0 (the number of items in our subset):ans
(max score): 0num
(number of items selected): 0cnt
(theCounter
for labels): {}
-
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 reachesnumWanted
, we stop selecting items.cnt
becomes {1: 1, 2: 1, 3: 1}
-
Return the maximum score:
Since we have selected the maximum number of items (
numWanted
), we returnans
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
.
Solution Implementation
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
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
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
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:
-
Sorting the combined list of values and labels:
sorted(zip(values, labels), reverse=True)
takesO(N log N)
time, whereN
is the length of the values (and labels) list. -
The
for
loop iterates over the sorted list, which hasN
elements. In the worst case, it will iterate over allN
elements once. -
Inside the loop, updating the
Counter
and performing basic arithmetic operations areO(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:
-
The additional space used by the sorted list of zipped values and labels is
O(N)
, whereN
is the length of the original lists. -
The
Counter
objectcnt
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 beO(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.
Learn more about how to find time and space complexity quickly using problem constraints.
Which data structure is used in a depth first search?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.