Domain 2MediumMEDIUM

Largest Values From Labels

Maximize sum of selected items by greedily picking highest values first while tracking global count and per-label usage limits.

Domain: medium•Updated: 2026-09-08
#Greedy#Hash Map (Dictionary)#Time Complexity O(N log N)#Space Complexity O(N)

Problem Breakdown

The problem requires selecting a subset of items to maximize the total value. There are two constraints limiting this selection:

  1. Global Limit: The total number of selected items cannot exceed num_wanted.
  2. Local Limit: For any specific label, we can select at most use_limit items 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 (O(2N)O(2^N)) due to the large input size (N≤20,000N \le 20,000). The optimal strategy relies on two observations:

  1. Greedy Choice Property: If we can pick an item with value VV, 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).
  2. 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_wanted is reached or no more candidates remain.

Approach

  1. Pairing Data: Combine the parallel arrays values and labels into a list of tuples (label, value). This preserves the association between an item’s label and its value during sorting.
  2. 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.
  3. Iteration & Validation: Iterate through the sorted items:
    • Maintain a global counter (count_picked) to track if we hit num_wanted.
    • Use a hash map (dictionary) (used_labels_count) to track how many times each label has been used so far. Check against use_limit for the current item’s label.
  4. 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: O(Nlog⁡N)O(N \log N). The sorting operation dominates the runtime complexity where NN is the number of items (20,00020,000). Iterating through the list and performing dictionary lookups takes linear time O(N)O(N) with average constant-time hash map operations.
  • Space Complexity: O(N)O(N). 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 (NN).

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