Problem Description

You have n items, each with a value and a label. These are given as two arrays: values and labels, where values[i] is the value of the i-th item and labels[i] is its label.

You need to select a subset of these items to maximize the total value, but with two constraints:

1. Total item limit: You can select at most numWanted items in total.
2. Per-label limit: For items with the same label, you can select at most useLimit of them.

The goal is to find the maximum possible sum of values you can achieve while respecting both constraints.

For example, if you have items with values [5, 4, 3, 2, 1] and labels [1, 1, 2, 2, 3], with numWanted = 3 and useLimit = 1, you would:

• Pick the item with value 5 and label 1 (used 1 item with label 1)
• Pick the item with value 3 and label 2 (used 1 item with label 2)
• Pick the item with value 1 and label 3 (used 1 item with label 3)
• Total sum = 5 + 3 + 1 = 9

Note that you couldn't pick the item with value 4 (label 1) because you already used 1 item with label 1, reaching the useLimit.

The solution uses a greedy approach: sort items by value in descending order, then greedily select items with the highest values while tracking how many items of each label have been used. The process stops when either numWanted items have been selected or no more valid items can be added.

Intuition

When we want to maximize the sum of values with constraints, a greedy approach often works well. The key insight is that we should prioritize items with higher values first, regardless of their labels.

Think of it like filling a basket with the most valuable items from a store, but with rules about how many of each type you can take. Naturally, you'd want to pick the most expensive items first, then work your way down to less valuable ones.

Why does this greedy strategy work here? Because:

1. Value is independent of label: An item's value doesn't depend on its label, so we can consider all items together and sort them by value alone.

2. No penalty for label diversity: There's no requirement to use items from different labels - we just have a limit on how many items with the same label we can use. This means if the top 3 most valuable items all have different labels and we can take 3 items total, we should take all of them.

3. Constraints are only limiting, not directing: The constraints (numWanted and useLimit) only restrict what we can take, they don't force us to take certain items. This makes the greedy approach optimal - we never need to "save space" for a less valuable item.

The strategy becomes clear: sort all items by value in descending order, then iterate through them, taking each item if:

• We haven't reached the total limit of numWanted items
• We haven't used useLimit items with this particular label yet

We use a counter to track how many items of each label we've used. This greedy approach guarantees the maximum sum because we always pick the next most valuable item that we're allowed to take.

Learn more about Greedy and Sorting patterns.

Solution Approach

The implementation follows the greedy strategy we identified:

1. Combine and Sort: First, we pair each value with its corresponding label using zip(values, labels), then sort these pairs in descending order by value using sorted(..., reverse=True). This ensures we process items from highest value to lowest.

2. Initialize Tracking Variables:

   • ans: Accumulates the sum of selected values
   • num: Counts how many items we've selected so far
   • cnt = Counter(): A dictionary-like structure that tracks how many items of each label we've used

3. Greedy Selection: We iterate through the sorted (value, label) pairs:

   for v, l in sorted(zip(values, labels), reverse=True):

   For each item, we check if we can add it:

   • if cnt[l] < useLimit: Check if we haven't exceeded the limit for this label

   If we can add the item:

   • cnt[l] += 1: Increment the count for this label
   • num += 1: Increment the total number of items selected
   • ans += v: Add the value to our running sum

4. Early Termination:

   if num == numWanted:
       break

   Once we've selected numWanted items, we stop immediately since we've reached the maximum number of items allowed.

5. Return Result: The function returns ans, which contains the maximum sum achievable.

The time complexity is O(n log n) due to sorting, where n is the number of items. The space complexity is O(n) for storing the sorted pairs and the counter, which in the worst case could have an entry for each unique label.

This approach is optimal because at each step, we make the locally best choice (picking the highest available value), which leads to the globally optimal solution.

Example Walkthrough

Let's walk through a concrete example to see how the greedy solution works.

Input:

• values = [9, 8, 8, 7, 6]
• labels = [0, 0, 0, 1, 1]
• numWanted = 3
• useLimit = 2

Step 1: Combine and Sort First, we pair values with labels and sort by value (descending):

[(9, 0), (8, 0), (8, 0), (7, 1), (6, 1)]

Step 2: Initialize Variables

• ans = 0 (running sum)
• num = 0 (items selected)
• cnt = Counter() (empty counter for label usage)

Step 3: Iterate and Select Items

Iteration 1: (9, 0)

• Check: cnt[0] < useLimit → 0 < 2 ✓
• Select this item!
• Update: cnt[0] = 1, num = 1, ans = 9

Iteration 2: (8, 0)

• Check: cnt[0] < useLimit → 1 < 2 ✓
• Select this item!
• Update: cnt[0] = 2, num = 2, ans = 17

Iteration 3: (8, 0)

• Check: cnt[0] < useLimit → 2 < 2 ✗
• Cannot select (already used 2 items with label 0)
• Skip this item

Iteration 4: (7, 1)

• Check: cnt[1] < useLimit → 0 < 2 ✓
• Select this item!
• Update: cnt[1] = 1, num = 3, ans = 24
• Check: num == numWanted → 3 == 3 ✓
• Stop! We've reached the item limit

Result: Maximum sum = 24

We selected items with values [9, 8, 7], using 2 items with label 0 and 1 item with label 1, respecting both the total limit (3 items) and per-label limit (at most 2 items per label).

Solution Implementation

Time and Space Complexity

Time Complexity: O(n log n) where n is the length of the values/labels arrays.

• The zip(values, labels) operation takes O(n) time to create pairs
• The sorted() function performs a comparison-based sort on these pairs, which takes O(n log n) time
• The for loop iterates through the sorted pairs at most n times (or until numWanted items are selected), performing O(1) operations in each iteration:
  • Checking cnt[l] < useLimit: O(1) average case for dictionary lookup
  • Updating cnt[l]: O(1) average case for dictionary update
  • Adding to ans and num: O(1)
  • Checking if num == numWanted: O(1)

The dominant operation is the sorting step, making the overall time complexity O(n log n).

Space Complexity: O(n) where n is the length of the input arrays.

• The zip(values, labels) creates a new iterable of pairs: O(n) space
• The sorted() function creates a new sorted list: O(n) space
• The Counter() dictionary cnt stores at most O(k) entries where k is the number of unique labels, and in the worst case k = n: O(n) space
• Other variables (ans, num) use constant space: O(1)

The total space complexity is O(n) due to the sorted list and the counter dictionary.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Not Understanding the Per-Label Limit

A common misconception is thinking that useLimit applies globally across all labels combined, rather than to each label individually. For example, with useLimit = 2, some might incorrectly think you can only use 2 items total regardless of their labels.

Incorrect Understanding:

# Wrong: Treating useLimit as a global constraint
total_items_used = 0
for value, label in sorted_pairs:
    if total_items_used < useLimit:  # WRONG!
        total_items_used += 1
        # ...

Correct Understanding:

# Right: useLimit applies per label
label_usage_count = Counter()
for value, label in sorted_pairs:
    if label_usage_count[label] < useLimit:  # Correct - check per label
        label_usage_count[label] += 1
        # ...

Pitfall 2: Forgetting Early Termination

Without the early termination check, the code might continue processing items even after selecting numWanted items, leading to incorrect results where too many items are selected.

Problematic Code:

for value, label in sorted_pairs:
    if label_usage_count[label] < useLimit:
        label_usage_count[label] += 1
        items_selected += 1
        total_sum += value
        # Missing break condition!

return total_sum  # Might have selected more than numWanted items

Solution: Always include the termination check immediately after selecting an item:

if items_selected == numWanted:
    break

Pitfall 3: Incorrect Sorting Order

Sorting in ascending order instead of descending would select the smallest values first, completely defeating the greedy strategy.

Wrong:

# This would pick smallest values first
value_label_pairs = sorted(zip(values, labels))  # Missing reverse=True

Correct:

# Pick largest values first for maximum sum
value_label_pairs = sorted(zip(values, labels), reverse=True)

Pitfall 4: Edge Case Handling

The code handles edge cases naturally, but it's important to understand them:

• When numWanted exceeds the total number of items available
• When useLimit is very large (larger than any label frequency)
• When all items have the same label

The current implementation handles these correctly because:

• The loop naturally terminates when all items are processed
• The Counter returns 0 for unseen labels, preventing KeyError
• The break condition prevents selecting more than numWanted items