Skip to main content
Talentd

Largest Values From Labels - Solution & Explanation

MediumArrayHash TableGreedySorting16 min readAsked at: Google
Practice this problem

Problem Statement

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:

  • The number of items is at most numWanted.
  • The number of items with the same label is at most 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.length
  • 1 <= n <= 2 * 104
  • 0 <= values[i], labels[i] <= 2 * 104
  • 1 <= numWanted, useLimit <= n

Approach Overview

Problem 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.

Approach 1: Greedy with Sorting

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to the sorting step.
Space Complexity: O(n) due to the items array and label count storage.

Try this approach in the editor →

Approach 2: Heap-based Greedy Using Priority Queue

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.

Code

C++JavaPythonC#

C++

Java

Python

C#

Complexity

Time Complexity: O(n log n) due to heap operations for each item.
Space Complexity: O(n) for the heap and label tracking.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy with Sorting

Time Complexity: O(n log n) due to the sorting step.
Space Complexity: O(n) due to the items array and label count storage.

Heap-based Greedy Using Priority Queue

Time Complexity: O(n log n) due to heap operations for each item.
Space Complexity: O(n) for the heap and label tracking.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy with SortingO(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.

Video Solution

Largest Values from Labels • Kevin Naughton Jr. • 19,839 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Largest Values From Labels easy or hard?
Largest Values From Labels is rated Medium difficulty. The challenge lies in recognizing the greedy strategy and enforcing label constraints efficiently. Once the sorting insight is clear, the implementation becomes straightforward.
How to solve Largest Values From Labels in O(n)?
A true O(n) solution is generally not feasible because the algorithm needs to process items in descending value order. That ordering requires sorting or a heap, both of which take O(n log n) time. Without ordering, the greedy choice of the highest-value item cannot be guaranteed.
What is the best approach for Largest Values From Labels?
The best approach is greedy with sorting. Pair each value with its label, sort items by value in descending order, and select items while tracking how many times each label is used. This ensures you always pick the highest-value valid item while respecting the label limit. The complexity is O(n log n) due to sorting.
Is Largest Values From Labels asked at Google/Amazon/Meta?
Greedy selection problems with constraints frequently appear in interviews at companies like Amazon, Google, and Meta. While this exact problem may not always appear, similar patterns involving sorting by value and enforcing category limits are common interview questions.
What data structure is used in Largest Values From Labels?
The solution typically uses arrays for storing value-label pairs, a hash map or counting array to track how many times each label has been selected, and optionally a max heap (priority queue) to retrieve the largest value efficiently.
What is the time complexity of Largest Values From Labels?
The optimal solution runs in O(n log n) time because the items must be sorted by value or processed using a max heap. After sorting, a single pass selects up to numWanted elements while checking label counts. Space complexity is O(n) for storing pairs and label usage counts.
Largest Values From Labels Python or Java solution approach?
Both Python and Java implementations follow the same strategy: combine values and labels, sort by value descending, maintain a map of label usage, and accumulate values until numWanted items are selected. The logic is identical across languages; only syntax differs.

Ready to solve this problem?

Practice Largest Values From Labels with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximize Y‑Sum by Picking a Triplet of Distinct X‑Values