Leetcode 1090: Largest Values From Labels
You are given two arrays,
values and labels, representing the value and label of items, respectively. Your goal is to choose a subset of items with the maximum sum of values such that the number of items selected is at most numWanted and no label appears more than useLimit times in the subset. Return the maximum possible sum of the values from the selected subset of items.Problem
Approach
Steps
Complexity
Input: The input consists of two arrays: `values` and `labels` of length `n`, where each element in `values` represents the value of the corresponding item, and each element in `labels` represents the label of the corresponding item. Additionally, you are given two integers: `numWanted` (the maximum number of items that can be selected) and `useLimit` (the maximum number of items that can be selected with the same label).
Example: Input: values = [10, 8, 5, 4, 3], labels = [1, 1, 2, 2, 3], numWanted = 3, useLimit = 1
Constraints:
• n == values.length == labels.length
• 1 <= n <= 2 * 10^4
• 0 <= values[i], labels[i] <= 2 * 10^4
• 1 <= numWanted, useLimit <= n
Output: Return the maximum sum of the values from the selected subset of items that satisfies the constraints on selection and label usage.
Example: Output: 18
Constraints:
• The maximum sum should be obtained by selecting the best possible combination of items while respecting the label constraints.
Goal: The goal is to select the subset of items that yields the maximum sum of values while ensuring that no more than `numWanted` items are chosen and that no label appears more than `useLimit` times.
Steps:
• 1. Sort the items by their values in descending order to prioritize the highest value items.
• 2. Track the frequency of each label as items are selected.
• 3. Select items one by one while ensuring that the total number of selected items does not exceed `numWanted`, and no label appears more than `useLimit` times.
Goal: The solution must efficiently handle large inputs while adhering to the problem's constraints.
Steps:
• 1 <= n <= 2 * 10^4
• The solution should be optimized to handle up to 20,000 items.
• The input arrays `values` and `labels` contain integer values between 0 and 20,000.
Assumptions:
• The input arrays `values` and `labels` are non-empty and contain valid values within the specified range.
• Input: Input: values = [10, 8, 5, 4, 3], labels = [1, 1, 2, 2, 3], numWanted = 3, useLimit = 1
• Explanation: The optimal subset of items with the highest values while respecting the label constraints is the first, third, and fifth items, yielding a total value of 10 + 5 + 3 = 18.
• Input: Input: values = [9, 8, 7, 6, 5], labels = [0, 0, 1, 1, 0], numWanted = 3, useLimit = 2
• Explanation: In this example, the best subset is the first, second, and third items, which gives the maximum sum of values: 9 + 8 + 7 = 24.
• Input: Input: values = [5, 4, 3, 2, 1], labels = [1, 1, 2, 2, 3], numWanted = 3, useLimit = 1
• Explanation: The subset chosen is the first, third, and fifth items with the sum of values: 5 + 3 + 1 = 9.
Approach: We can solve this problem using a greedy approach where we prioritize selecting items with the highest values while ensuring that the label constraints are satisfied.
Observations:
• We need to ensure that the number of items selected does not exceed `numWanted`, and no label appears more than `useLimit` times.
• Sorting the items by value and then iterating over them while respecting the label constraints will allow us to efficiently find the optimal solution.
Steps:
• 1. Sort the items in descending order by value to maximize the sum.
• 2. Iterate over the sorted items and select them if they do not violate the `useLimit` for their label.
• 3. Keep track of the count of items selected for each label and ensure that no label exceeds `useLimit`.
• 4. Stop when `numWanted` items are selected.
Empty Inputs:
• If the input arrays `values` and `labels` are empty, the result should be 0.
Large Inputs:
• For large inputs, the algorithm should handle up to 20,000 items efficiently, ensuring that the solution works within the time limits.
Special Values:
• If all items have the same label, the solution should ensure that no more than `useLimit` items with the same label are selected.
Constraints:
• The algorithm should respect the constraints on the number of items selected and the label limitations.
int largestValsFromLabels(vector<int>& values, vector<int>& labels, int numWanted, int useLimit) {
multimap<int, int> s;
unordered_map<int, int> m;
for(int i = 0; i < values.size(); i++)
s.insert({values[i], labels[i]});
int res = 0;
for(auto it = rbegin(s); it != rend(s) && numWanted > 0; it++) {
if(++m[it->second] <= useLimit) {
res += it->first;
--numWanted;
}
}
return res;
}
1 : Function Definition
int largestValsFromLabels(vector<int>& values, vector<int>& labels, int numWanted, int useLimit) {
This line defines the function `largestValsFromLabels`, which takes four parameters: `values`, `labels`, `numWanted`, and `useLimit`.
2 : Variable Initialization - Multimap
multimap<int, int> s;
A multimap `s` is initialized to store pairs of values and their corresponding labels, with the ability to store multiple values with the same key.
3 : Variable Initialization - Unordered Map
unordered_map<int, int> m;
An unordered map `m` is initialized to count how many times a label has been used.
4 : Loop - Insert Values and Labels
for(int i = 0; i < values.size(); i++)
This loop iterates through the `values` vector and inserts each value with its corresponding label into the multimap `s`.
5 : Insert Pair into Multimap
s.insert({values[i], labels[i]});
Each pair of value and label is inserted into the multimap `s`, where the value will be sorted in ascending order by default.
6 : Result Initialization
int res = 0;
The variable `res` is initialized to 0. It will hold the sum of the selected largest values.
7 : Loop - Process Values
for(auto it = rbegin(s); it != rend(s) && numWanted > 0; it++) {
This loop iterates through the multimap `s` in reverse order, processing the largest values first. The loop continues until `numWanted` becomes 0.
8 : Condition - Label Usage Limit Check
if(++m[it->second] <= useLimit) {
This condition checks if the label of the current item has been used fewer times than the allowed limit (`useLimit`). If the condition is true, the value is included in the sum.
9 : Add Value to Result
res += it->first;
The value (`it->first`) from the current multimap entry is added to the result sum `res`.
10 : Decrement numWanted
--numWanted;
Since one value has been added to the result, `numWanted` is decremented to track how many more values need to be selected.
11 : Return Result
return res;
The function returns the result, which is the sum of the largest values that have been selected.
Best Case: O(n log n)
Average Case: O(n log n)
Worst Case: O(n log n)
Description: The sorting step dominates the time complexity, which is O(n log n) where n is the number of items.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) due to the need to store the items and track their labels and counts.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus