Problem Breakdown
The problem requires selecting a subset of items to maximize the total value. There are two constraints limiting this selection:
- Global Limit: The total number of selected items cannot exceed
num_wanted. - Local Limit: For any specific label, we can select at most
use_limititems with that label.
To achieve the maximum sum, we must prioritize items with higher values. This suggests a greedy strategy: always pick the available item with the highest value if it does not violate either constraint. Since picking an item consumes one slot from both the global quota and its specific label’s limit, sorting by value ensures we never “waste” high-value slots on lower-value alternatives that could have been picked later anyway (assuming limits allow).
Intuition
A brute-force search over all subsets is infeasible () due to the large input size (). The optimal strategy relies on two observations:
- Greedy Choice Property: If we can pick an item with value , and there exists another valid subset of items that includes a lower-value item instead but satisfies constraints, swapping the higher-value item in for the lower one will always yield a better or equal sum without violating constraints (since limits are counts).
- Sorting Priority: By sorting all available items by their value in descending order, we can iterate through them and pick every valid candidate until either
num_wantedis reached or no more candidates remain.
Approach
- Pairing Data: Combine the parallel arrays
valuesandlabelsinto a list of tuples(label, value). This preserves the association between an item’s label and its value during sorting. - Sorting: Sort this paired list in descending order based on the
value. Python’s sort is stable, but for correctness here, we strictly prioritize by value magnitude. - Iteration & Validation: Iterate through the sorted items:
- Maintain a global counter (
count_picked) to track if we hitnum_wanted. - Use a hash map (dictionary) (
used_labels_count) to track how many times each label has been used so far. Check againstuse_limitfor the current item’s label.
- Maintain a global counter (
- Accumulation: If both checks pass, add the value to the running sum and increment counters. Stop implicitly when either limit is reached (the condition fails).
Complexity Analysis
- Time Complexity: . The sorting operation dominates the runtime complexity where is the number of items (). Iterating through the list and performing dictionary lookups takes linear time with average constant-time hash map operations.
- Space Complexity: . We store a list of tuples for sorting (or modify in place depending on implementation details), plus a hash map to track label usage which can grow up to the number of unique labels ().
Solution
from collections import defaultdict
def largestValsFromLabels(values, labels, num_wanted, use_limit):
# Pair each label with its value and sort by value in descending order.
paired = sorted(zip(labels, values), key=lambda x: -x[1])
used_labels_count = defaultdict(int)
count_picked = 0
max_sum = 0
for label, val in paired:
# Check if we can pick this item based on global quota and specific label limit.
if count_picked < num_wanted and used_labels_count[label] < use_limit:
max_sum += val
used_labels_count[label] += 1
count_picked += 1
return max_sum
```python
from collections import defaultdict
def largestValsFromLabels(values, labels, num_wanted, use_limit):
# Pair each label with its value and sort by value in descending order.
paired = sorted(zip(labels, values), key=lambda x: -x[1])
used_labels_count = defaultdict(int)
count_picked = 0
max_sum = 0
for label, val in paired:
# Check if we can pick this item based on global quota and specific label limit.
if count_picked < num_wanted and used_labels_count[label] < use_limit:
max_sum += val
used_labels_count[label] += 1
count_picked += 1
return max_sum