LeetCode 1090 - Largest Values From Labels

LeetCode Problem 1090

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Greedy, Sorting, Counting

Solution

Problem Understanding

The problem gives us two arrays, values and labels, where each index represents a single item. The item at index i has a value values[i] and a category or group identifier labels[i].

We want to choose a subset of these items such that two constraints are satisfied:

• We can select at most numWanted total items.
• For any specific label, we can select at most useLimit items with that label.

Among all valid subsets, we must maximize the total sum of selected values.

The important detail is that the optimization target is purely the sum of values. Labels only act as restrictions that limit how many items from the same category can be chosen.

For example, if several items have extremely large values but all share the same label, we may not be allowed to take all of them because of the useLimit restriction. This forces us to balance selecting high-value items with respecting per-label limits.

The constraints are important because they tell us what kind of algorithm is feasible:

• n can be as large as 2 * 10^4
• Values and labels are integers up to 2 * 10^4

A brute-force search over all subsets would be impossible because the number of subsets grows exponentially. With n = 20000, even checking all subsets is completely infeasible.

The constraints strongly suggest that we need a greedy or sorting-based solution with roughly O(n log n) complexity.

Several edge cases are worth thinking about immediately:

• Multiple large values may share the same label, causing the label limit to become the bottleneck.
• numWanted may be larger than the number of items we are actually allowed to take.
• Some values may be zero, meaning selecting them may not improve the answer.
• All items may share the same label.
• useLimit may be 1, which means we can only take one item per label.
• The optimal solution may use fewer than numWanted items because label restrictions prevent additional selections.

The problem guarantees that both arrays have the same length and that all constraints are valid, so we do not need to handle malformed input.

Approaches

Brute Force Approach

The brute-force idea is to examine every possible subset of items. For each subset, we would:

1. Count how many items were selected.
2. Count how many times each label appears.
3. Verify the subset satisfies both constraints.
4. Compute the total value.
5. Track the maximum valid sum.

This approach is correct because it literally checks every possible solution and chooses the best one.

However, it is far too slow. A set of n items has 2^n possible subsets. Even for n = 30, this is already too large. Since the actual limit is 20000, brute force is completely impossible.

Key Insight for the Optimal Solution

The critical observation is that we always prefer larger values over smaller values whenever possible.

Suppose we have two items with the same label and one has a larger value. If we are allowed to take only one of them, we should always take the larger one.

This naturally leads to a greedy strategy:

1. Sort all items in descending order of value.
2. Iterate through items from largest to smallest.
3. Select an item if:

• We still have room under numWanted
• Its label has not exceeded useLimit

Because we process items from highest value to lowest value, every selection is locally optimal. If an item can legally be included, taking it immediately is always beneficial because any later item will have equal or smaller value.

We use a hash map to track how many times each label has already been used.

This gives an efficient O(n log n) solution dominated by sorting.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n * n)	O(n)	Enumerates all subsets and validates each one
Optimal	O(n log n)	O(n)	Greedy selection after sorting by value

Algorithm Walkthrough

1. Combine each item's value and label into a single pair.

We need to process both pieces of information together, so storing them as tuples like (value, label) makes the algorithm easier to implement. 2. Sort all items in descending order by value.

This is the core greedy step. By examining the largest values first, we maximize the total sum as early as possible. 3. Create a hash map to track label usage.

The map stores how many times each label has already been selected. This allows constant-time checks against useLimit. 4. Initialize variables for:

• The running total sum
• The number of selected items

5. Iterate through the sorted items.

For each (value, label) pair:

• Check whether the label has already reached useLimit.

• If it has, skip the item.

• Otherwise:

• Add the value to the answer

• Increment the label count

• Increment the selected item count

6. Stop once numWanted items have been selected.

Since items are processed in descending order, once we have selected enough items, no remaining item can improve the answer. 7. Return the accumulated sum.

Why it works

The algorithm works because of the greedy ordering.

At every step, we consider the largest remaining value. If selecting it does not violate constraints, then taking it is always optimal because every future candidate has value less than or equal to the current one.

The invariant is:

• After processing the first k items in sorted order, the chosen subset has the maximum possible sum among all valid subsets using only those k items.

Since the algorithm never skips a valid higher-value item in favor of a lower-value one, the final result is globally optimal.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def largestValsFromLabels(
        self,
        values: List[int],
        labels: List[int],
        numWanted: int,
        useLimit: int
    ) -> int:

        items = list(zip(values, labels))

        # Sort by value descending
        items.sort(reverse=True)

        label_count = defaultdict(int)

        total_sum = 0
        selected = 0

        for value, label in items:

            if label_count[label] >= useLimit:
                continue

            total_sum += value
            label_count[label] += 1
            selected += 1

            if selected == numWanted:
                break

        return total_sum

The implementation begins by pairing each value with its corresponding label using zip. This creates a convenient structure for sorting and processing.

Next, the items are sorted in descending order. Python tuple sorting automatically prioritizes the first element, which is the value.

A defaultdict(int) is used to track how many times each label has been selected. This avoids manual initialization checks.

The loop processes items from highest value to lowest value. If a label has already reached useLimit, the item is skipped. Otherwise, the value is added to the answer and the label count is updated.

The algorithm stops early once numWanted items have been chosen. This optimization avoids unnecessary processing.

Finally, the accumulated maximum sum is returned.

Go Solution

package main

import "sort"

func largestValsFromLabels(values []int, labels []int, numWanted int, useLimit int) int {

	type Item struct {
		value int
		label int
	}

	n := len(values)

	items := make([]Item, n)

	for i := 0; i < n; i++ {
		items[i] = Item{
			value: values[i],
			label: labels[i],
		}
	}

	sort.Slice(items, func(i, j int) bool {
		return items[i].value > items[j].value
	})

	labelCount := make(map[int]int)

	totalSum := 0
	selected := 0

	for _, item := range items {

		if labelCount[item.label] >= useLimit {
			continue
		}

		totalSum += item.value
		labelCount[item.label]++
		selected++

		if selected == numWanted {
			break
		}
	}

	return totalSum
}

The Go implementation follows the same logic as the Python version but uses a custom Item struct to store value-label pairs.

Sorting is performed with sort.Slice, using a custom comparator that orders items by descending value.

A map[int]int tracks label usage counts. Go maps return zero values automatically for missing keys, so explicit initialization is unnecessary.

Since all values fit comfortably within standard integer limits under the problem constraints, integer overflow is not a concern in Go.

Worked Examples

Example 1

Input:

values = [5,4,3,2,1]
labels = [1,1,2,2,3]
numWanted = 3
useLimit = 1

After pairing and sorting:

Value	Label
5	1
4	1
3	2
2	2
1	3

Processing steps:

Step	Item	Label Count Before	Action	Total Sum
1	(5,1)	0	Take	5
2	(4,1)	1	Skip, limit reached	5
3	(3,2)	0	Take	8
4	(2,2)	1	Skip, limit reached	8
5	(1,3)	0	Take	9

Selected items:

5 + 3 + 1 = 9

Final answer:

9

Example 2

Input:

values = [5,4,3,2,1]
labels = [1,3,3,3,2]
numWanted = 3
useLimit = 2

Sorted items:

Value	Label
5	1
4	3
3	3
2	3
1	2

Processing:

Step	Item	Label Count Before	Action	Total Sum
1	(5,1)	0	Take	5
2	(4,3)	0	Take	9
3	(3,3)	1	Take	12

We already selected numWanted = 3 items, so the algorithm stops.

Final answer:

12

Example 3

Input:

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

Sorted items:

Value	Label
9	0
8	0
8	0
7	1
6	1

Processing:

Step	Item	Label Count Before	Action	Total Sum
1	(9,0)	0	Take	9
2	(8,0)	1	Skip	9
3	(8,0)	1	Skip	9
4	(7,1)	0	Take	16
5	(6,1)	1	Skip	16

Final answer:

16

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates the runtime
Space	O(n)	Storage for item pairs and label counts

The sorting step requires O(n log n) time, which is the dominant operation. The iteration afterward is linear.

The space complexity is O(n) because we store all item pairs and maintain a hash map for label frequencies.

Test Cases

from typing import List
from collections import defaultdict

class Solution:
    def largestValsFromLabels(
        self,
        values: List[int],
        labels: List[int],
        numWanted: int,
        useLimit: int
    ) -> int:

        items = list(zip(values, labels))
        items.sort(reverse=True)

        label_count = defaultdict(int)

        total_sum = 0
        selected = 0

        for value, label in items:

            if label_count[label] >= useLimit:
                continue

            total_sum += value
            label_count[label] += 1
            selected += 1

            if selected == numWanted:
                break

        return total_sum

sol = Solution()

# Example 1
assert sol.largestValsFromLabels(
    [5,4,3,2,1],
    [1,1,2,2,3],
    3,
    1
) == 9  # basic label restriction

# Example 2
assert sol.largestValsFromLabels(
    [5,4,3,2,1],
    [1,3,3,3,2],
    3,
    2
) == 12  # multiple allowed per label

# Example 3
assert sol.largestValsFromLabels(
    [9,8,8,7,6],
    [0,0,0,1,1],
    3,
    1
) == 16  # skipping large duplicates by label

# Single item
assert sol.largestValsFromLabels(
    [10],
    [1],
    1,
    1
) == 10  # minimum input size

# All labels unique
assert sol.largestValsFromLabels(
    [1,2,3,4],
    [1,2,3,4],
    2,
    1
) == 7  # simply choose top two values

# All labels identical
assert sol.largestValsFromLabels(
    [9,8,7,6],
    [1,1,1,1],
    3,
    2
) == 17  # can only take two largest

# numWanted larger than feasible
assert sol.largestValsFromLabels(
    [5,4,3],
    [1,1,1],
    3,
    1
) == 5  # label restriction prevents more selections

# Zero values
assert sol.largestValsFromLabels(
    [0,0,10],
    [1,2,3],
    3,
    1
) == 10  # zero-value items handled correctly

# useLimit equals numWanted
assert sol.largestValsFromLabels(
    [10,9,8],
    [1,1,1],
    3,
    3
) == 27  # all items selectable

# Large values mixed labels
assert sol.largestValsFromLabels(
    [100,90,80,70],
    [1,1,2,2],
    3,
    1
) == 170  # best combination under constraints

Test	Why
Example 1	Verifies basic greedy selection
Example 2	Confirms multiple selections per label
Example 3	Ensures oversized label groups are skipped
Single item	Smallest valid input
All labels unique	No label conflicts
All labels identical	Strong label restriction
numWanted larger than feasible	Cannot always select desired count
Zero values	Handles non-contributing items
useLimit equals numWanted	Constraint effectively removed
Large values mixed labels	Tests balancing between labels

Edge Cases

One important edge case occurs when all items share the same label. In this scenario, the useLimit becomes the true cap on how many items can be selected, regardless of numWanted. A buggy implementation might continue selecting too many items because it only tracks the total count. The solution avoids this by maintaining exact per-label counts in the hash map.

Another important case is when numWanted is larger than the number of items that can legally be selected. For example, if all items share one label and useLimit = 1, we may only be able to choose a single item even if numWanted = 10. The implementation handles this naturally because it only selects valid items and simply finishes iterating when no more valid choices remain.

A third edge case involves duplicate high values from the same label. Consider several top-valued items all belonging to one label while the limit is small. A naive greedy implementation that does not enforce label counts carefully might incorrectly choose too many from the same group. This solution checks the label count before every selection, ensuring constraints are always respected.

Another subtle case is when values contain zeros. Since the goal is maximizing the sum, selecting zero-value items is only useful if they help fill available slots and remain valid under label constraints. The greedy ordering still works correctly because larger positive values are processed first, and zero-value items are only selected if nothing better remains.