#1090

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Largest Values From Labels

Maximize the sum of selected item values while respecting label use limits using array scanning and hash tracking.

array hash table greedy sorting counting

Problem Statement

You are given two integer arrays, values and labels, representing the value and label of n items, along with two integers numWanted and useLimit. Your task is to select a subset of items to maximize the sum of their values, ensuring that no more than useLimit items with the same label are chosen and the total number of items does not exceed numWanted.

Return the maximum sum achievable under these constraints. Each item can be chosen at most once, and you must consider the interplay between value prioritization and label limits to achieve the optimal subset.

Examples

Example 1

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

Output: 9

The subset chosen is the first, third, and fifth items with the sum of values 5 + 3 + 1.

Example 2

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

Output: 12

The subset chosen is the first, second, and third items with the sum of values 5 + 4 + 3.

Example 3

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

Output: 16

The subset chosen is the first and fourth items with the sum of values 9 + 7.

Constraints

n == values.length == labels.length
1 <= n <= 2 * 104
0 <= values[i], labels[i] <= 2 * 104
1 <= numWanted, useLimit <= n

Solution Approach

Sort Items by Value Descending

Start by pairing each value with its corresponding label and sort all items in descending order of value. Sorting ensures that when scanning the array, the highest-value items are considered first, which aligns with the greedy strategy for maximizing the sum under label constraints.

Track Label Usage with Hash Map

Use a hash map to count how many times each label has been included in the selected subset. Before adding an item to the result sum, check if the label's current count is below useLimit. This prevents over-selection of any single label while enabling efficient lookups during the array scan.

Greedy Selection Under numWanted Limit

Iterate through the sorted items and select each item if its label count is under useLimit, stopping once numWanted items are chosen. This approach ensures the highest-value items are included first while respecting both per-label and overall selection limits, directly applying the array scanning plus hash lookup pattern.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Sorting takes O(n log n) time, and iterating through the sorted array with hash lookups is O(n). Space complexity is O(n) due to storing the label counts in a hash map.

What Interviewers Usually Probe

They may emphasize handling the label use limit efficiently and checking edge cases where multiple items share the same label.
Expect questions on whether your greedy strategy guarantees the optimal solution and why sorting is necessary for this pattern.
They may probe for time and space optimization, especially how the hash map prevents scanning the array repeatedly for label counts.

Common Pitfalls or Variants

Common pitfalls

Failing to sort the items by value first can lead to suboptimal selection and incorrect maximum sum.
Ignoring the useLimit per label, which may exceed allowed selections and produce invalid answers.
Stopping iteration too early or not checking numWanted accurately, leading to incomplete subsets or unused slots.

Follow-up variants

Allowing items to be selected multiple times per label, which shifts the problem from greedy selection to dynamic programming.
Adding negative values or zero-value items, requiring careful handling to avoid decreasing the sum.
Restricting the total number of unique labels instead of individual useLimit, which changes the hash tracking logic.

FAQ

What is the core pattern used in Largest Values From Labels?

The problem uses an array scanning plus hash lookup pattern, sorting items by value and tracking label counts to select the maximum subset sum.

Why is sorting items by value important?

Sorting ensures the greedy selection considers the highest-value items first, which is essential to maximize the sum under numWanted and useLimit constraints.

How do I handle the useLimit per label?

Maintain a hash map counting how many times each label is selected. Only add an item if its label count is below useLimit.

Can this problem be solved without a hash map?

Technically yes, but without a hash map you would need repeated scans of the array to count labels, which increases time complexity.

What is the time complexity of this solution?

The dominant factor is sorting, which is O(n log n), followed by a linear scan with hash lookups, resulting in overall O(n log n) time and O(n) space.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def largestValsFromLabels(
        self, values: List[int], labels: List[int], numWanted: int, useLimit: int
    ) -> int:
        ans = num = 0
        cnt = Counter()
        for v, l in sorted(zip(values, labels), reverse=True):
            if cnt[l] < useLimit:
                cnt[l] += 1
                num += 1
                ans += v
                if num == numWanted:
                    break
        return ans

Continue Practicing

#1054 distant barcodes #1481 least number of unique integers after k removals #621 task scheduler