You are given n item's value and label as two integer arrays values and labels. You are also given two integers numWanted and useLimit.
Your task is to find a subset of items with the maximum sum of their values such that:
numWanted.useLimit.Return the maximum sum.
Example 1:
Input: values = [5,4,3,2,1], labels = [1,1,2,2,3], numWanted = 3, useLimit = 1
Output: 9
Explanation:
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
Explanation:
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
Explanation:
The subset chosen is the first and fourth items with the sum of values 9 + 7.
Constraints:
n == values.length == labels.length1 <= n <= 2 * 1040 <= values[i], labels[i] <= 2 * 1041 <= numWanted, useLimit <= nProblem Overview: You are given two arrays: values and labels. Each item has a value and a label. You may choose at most numWanted items, but each label can only be used up to useLimit times. The goal is to maximize the total value of the selected items.
Approach 1: Greedy with Sorting (O(n log n) time, O(n) space)
The key observation is that the objective is purely value maximization with a constraint on how many times a label can appear. That naturally suggests a greedy strategy: always try to take the highest-value items first. Pair each value with its label, then sort the items in descending order by value using a sorting step. Iterate through the sorted list and keep selecting items while tracking how many times each label has been used.
A simple counter structure such as a hash map or array keeps the usage count for every label. If the current item's label has been used fewer than useLimit times, include it and add its value to the result. Stop once numWanted items have been chosen. Sorting dominates the runtime, giving O(n log n) time, while the label counter uses O(n) space in the worst case.
Approach 2: Heap-based Greedy Using Priority Queue (O(n log n) time, O(n) space)
This version replaces explicit sorting with a max-heap (priority queue). Insert all items into a heap ordered by value. Each step pops the largest available value, checks the label usage, and decides whether to include the item. Label frequencies are tracked using a hash table.
The heap ensures that every extraction returns the current highest-value candidate. Continue popping until either numWanted valid items are selected or the heap becomes empty. Heap insertion and removal cost O(log n), so processing all elements results in O(n log n) time with O(n) space for the heap and label counts.
Recommended for interviews: The greedy sorting approach is the most common solution expected in interviews. It clearly demonstrates the correct insight: prioritize the highest values while enforcing label limits with a simple counter. Implementing the heap version shows familiarity with priority queues, but sorting is shorter, easier to reason about, and typically preferred during coding rounds.
Sort the items based on their values in descending order. This ensures you always consider adding the highest value remaining item. Use a hash map or dictionary to track how many items with a particular label have been used so far. Iterate through the sorted items and add them to the result if they do not exceed the use limit for their label and if you have not yet reached numWanted items in total.
This C solution defines a structure to hold items with their value and label, sorts these items by value in descending order, and iterates through them to collect the maximum possible sum without exceeding the use limit for any label or the total number of items.
Time Complexity: O(n log n) due to the sorting step.
Space Complexity: O(n) due to the items array and label count storage.
Use a max heap (priority queue) to efficiently get the highest value item each time. Push tuples of negative values and their indices into the heap for all items. Then extract items from the heap, ensuring you do not exceed the use limit for any label and stop when numWanted items are chosen.
This C++ solution uses a priority queue to maintain a max-heap of items based on their values. The items are retrieved in order of their values, and selected if they do not violate the label count restrictions.
Time Complexity: O(n log n) due to heap operations for each item.
Space Complexity: O(n) for the heap and label tracking.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Greedy with Sorting | Time Complexity: O(n log n) due to the sorting step. |
| Heap-based Greedy Using Priority Queue | Time Complexity: O(n log n) due to heap operations for each item. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Sorting | O(n log n) | O(n) | Best general solution. Simple implementation and commonly expected in interviews. |
| Heap-based Greedy (Priority Queue) | O(n log n) | O(n) | Useful when data is streamed or when you want incremental access to the largest values. |
Largest Values from Labels • Kevin Naughton Jr. • 19,815 views views
Watch 9 more video solutions →Practice Largest Values From Labels with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor