1090. Largest Values From Labels - Solution

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

The problem

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 * 10⁴
0 <= values[i], labels[i] <= 2 * 10⁴
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.

Python

from collections import defaultdict

class Solution:
    def largestValsFromLabels(self, values, labels, numWanted, useLimit):
        items = list(zip(values, labels))
        items.sort(reverse=True, key=lambda x: x[0])

        label_count = defaultdict(int)
        total_value = 0
        num_chosen = 0

        for value, label in items:
            if num_chosen == numWanted:
                break
            if label_count[label] < useLimit:
                total_value += value
                label_count[label] += 1
                num_chosen += 1

        return total_value

# Example usage
solution = Solution()
values = [5, 4, 3, 2, 1]
labels = [1, 1, 2, 2, 3]
numWanted = 3
useLimit = 1
print("Maximum sum:", solution.largestValsFromLabels(values, labels, numWanted, useLimit))

Java

import java.util.*;

class Solution {
    private static class Item {
        int value;
        int label;

        Item(int v, int l) {
            value = v;
            label = l;
        }
    }

    public int largestValsFromLabels(int[] values, int[] labels, int numWanted, int useLimit) {
        List<Item> items = new ArrayList<>();
        for (int i = 0; i < values.length; i++) {
            items.add(new Item(values[i], labels[i]));
        }
        items.sort((a, b) -> b.value - a.value);

        Map<Integer, Integer> labelCount = new HashMap<>();
        int totalValue = 0;
        int numChosen = 0;

        for (Item item : items) {
            if (numChosen == numWanted) break;
            labelCount.putIfAbsent(item.label, 0);
            if (labelCount.get(item.label) < useLimit) {
                totalValue += item.value;
                labelCount.put(item.label, labelCount.get(item.label) + 1);
                numChosen++;
            }
        }
        return totalValue;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] values = {5, 4, 3, 2, 1};
        int[] labels = {1, 1, 2, 2, 3};
        int numWanted = 3;
        int useLimit = 1;
        System.out.println("Maximum sum: " + solution.largestValsFromLabels(values, labels, numWanted, useLimit));
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

struct Item {
    int value;
    int label;
};

bool compare(Item a, Item b) {
    return a.value > b.value;
}

int largestValsFromLabels(vector<int>& values, vector<int>& labels, int numWanted, int useLimit) {
    vector<Item> items;
    for (size_t i = 0; i < values.size(); ++i) {
        items.push_back({values[i], labels[i]});
    }
    sort(items.begin(), items.end(), compare);

    unordered_map<int, int> labelCounts;
    int totalValue = 0;
    int numChosen = 0;

    for (const auto& item : items) {
        if (numChosen == numWanted) break;
        if (labelCounts[item.label] < useLimit) {
            totalValue += item.value;
            labelCounts[item.label]++;
            numChosen++;
        }
    }
    return totalValue;
}

int main() {
    vector<int> values = {5,4,3,2,1};
    vector<int> labels = {1,1,2,2,3};
    int numWanted = 3;
    int useLimit = 1;
    cout << "Maximum sum: " << largestValsFromLabels(values, labels, numWanted, useLimit) << endl;
    return 0;
}

JavaScript

function largestValsFromLabels(values, labels, numWanted, useLimit) {
    const items = values.map((value, idx) => ({ value, label: labels[idx] }));
    items.sort((a, b) => b.value - a.value);

    const labelCount = {};
    let totalValue = 0;
    let numChosen = 0;

    for (const item of items) {
        if (numChosen === numWanted) break;
        if (!labelCount[item.label]) labelCount[item.label] = 0;
        if (labelCount[item.label] < useLimit) {
            totalValue += item.value;
            labelCount[item.label]++;
            numChosen++;
        }
    }

    return totalValue;
}

// Example usage
const values = [5, 4, 3, 2, 1];
const labels = [1, 1, 2, 2, 3];
const numWanted = 3;
const useLimit = 1;
console.log("Maximum sum:", largestValsFromLabels(values, labels, numWanted, useLimit));

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int value;
    int label;
} Item;

int cmp(const void *a, const void *b) {
    return ((Item*)b)->value - ((Item*)a)->value;
}

int largestValsFromLabels(int* values, int valuesSize, int* labels, int labelsSize, int numWanted, int useLimit) {
    Item items[valuesSize];
    for (int i = 0; i < valuesSize; i++) {
        items[i].value = values[i];
        items[i].label = labels[i];
    }
    qsort(items, valuesSize, sizeof(Item), cmp);

    int labelCount[20001] = {0};
    int totalValue = 0;
    int numChosen = 0;

    for (int i = 0; i < valuesSize && numChosen < numWanted; i++) {
        if (labelCount[items[i].label] < useLimit) {
            totalValue += items[i].value;
            labelCount[items[i].label]++;
            numChosen++;
        }
    }

    return totalValue;
}

int main() {
    int values[] = {5,4,3,2,1};
    int labels[] = {1,1,2,2,3};
    int numWanted = 3;
    int useLimit = 1;
    int result = largestValsFromLabels(values, 5, labels, 5, numWanted, useLimit);
    printf("Maximum sum: %d\n", result);
    return 0;
}

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public int LargestValsFromLabels(int[] values, int[] labels, int numWanted, int useLimit) {
        var items = values.Zip(labels, (v, l) => new { Value = v, Label = l }).ToList();
        items.Sort((a, b) => b.Value.CompareTo(a.Value));

        Dictionary<int, int> labelCount = new Dictionary<int, int>();
        int totalValue = 0;
        int numChosen = 0;

        foreach (var item in items) {
            if (numChosen == numWanted) break;
            if (!labelCount.ContainsKey(item.Label))
                labelCount[item.Label] = 0;
            if (labelCount[item.Label] < useLimit) {
                totalValue += item.Value;
                labelCount[item.Label]++;
                numChosen++;
            }
        }

        return totalValue;
    }

    public static void Main(string[] args) {
        Solution solution = new Solution();
        int[] values = { 5, 4, 3, 2, 1 };
        int[] labels = { 1, 1, 2, 2, 3 };
        int numWanted = 3;
        int useLimit = 1;
        Console.WriteLine("Maximum sum: " + solution.LargestValsFromLabels(values, labels, numWanted, useLimit));
    }
}

This Python solution leverages a tuple to store values and labels together and uses a descending sort to prioritize higher values. A defaultdict tracks the count of each label used, and items are selected based on the numWanted and useLimit constraints.

Complexity

Time Complexity: O(n log n) for sorting the items.
Space Complexity: O(n) for storing the tuples and label count dictionary.

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.

Python

import heapq

class Solution:
    def largestValsFromLabels(self, values, labels, numWanted, useLimit):
        heap = [(-v, l) for v, l in zip(values, labels)]
        heapq.heapify(heap)

        label_count = defaultdict(int)
        total_value = 0
        num_chosen = 0

        while heap and num_chosen < numWanted:
            value, label = heapq.heappop(heap)
            value = -value  # negate back to positive
            if label_count[label] < useLimit:
                total_value += value
                label_count[label] += 1
                num_chosen += 1

        return total_value

# Example usage
solution = Solution()
values = [5, 4, 3, 2, 1]
labels = [1, 1, 2, 2, 3]
numWanted = 3
useLimit = 1
print("Maximum sum:", solution.largestValsFromLabels(values, labels, numWanted, useLimit))

Java

import java.util.*;

class Solution {
    public int largestValsFromLabels(int[] values, int[] labels, int numWanted, int useLimit) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        for (int i = 0; i < values.length; i++) {
            pq.offer(new int[]{values[i], labels[i]});
        }

        Map<Integer, Integer> labelCount = new HashMap<>();
        int totalValue = 0;
        int numChosen = 0;

        while (!pq.isEmpty() && numChosen < numWanted) {
            int[] item = pq.poll();
            if (labelCount.getOrDefault(item[1], 0) < useLimit) {
                totalValue += item[0];
                labelCount.put(item[1], labelCount.getOrDefault(item[1], 0) + 1);
                numChosen++;
            }
        }
        return totalValue;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] values = {5, 4, 3, 2, 1};
        int[] labels = {1, 1, 2, 2, 3};
        int numWanted = 3;
        int useLimit = 1;
        System.out.println("Maximum sum: " + solution.largestValsFromLabels(values, labels, numWanted, useLimit));
    }
}

C++

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>

using namespace std;

int largestValsFromLabels(vector<int>& values, vector<int>& labels, int numWanted, int useLimit) {
    priority_queue<pair<int, int>> pq;
    for (int i = 0; i < values.size(); ++i) {
        pq.push({values[i], labels[i]});
    }

    unordered_map<int, int> labelCount;
    int totalValue = 0;
    int numChosen = 0;

    while (!pq.empty() && numChosen < numWanted) {
        auto [value, label] = pq.top(); pq.pop();
        if (labelCount[label] < useLimit) {
            totalValue += value;
            labelCount[label]++;
            numChosen++;
        }
    }
    return totalValue;
}

int main() {
    vector<int> values = {5, 4, 3, 2, 1};
    vector<int> labels = {1, 1, 2, 2, 3};
    int numWanted = 3;
    int useLimit = 1;
    cout << "Maximum sum: " << largestValsFromLabels(values, labels, numWanted, useLimit) << endl;
    return 0;
}

using System;
using System.Collections.Generic;

public class Solution {
    public int LargestValsFromLabels(int[] values, int[] labels, int numWanted, int useLimit) {
        SortedSet<(int value, int label, int index)> pq = new SortedSet<(int value, int label, int index)>(Comparer<(int, int, int)>.Create((a, b) => 
        (b.value == a.value) ? a.index.CompareTo(b.index) : b.value.CompareTo(a.value)));
        for (int i = 0; i < values.Length; i++) {
            pq.Add((values[i], labels[i], i));
        }

        Dictionary<int, int> labelCount = new Dictionary<int, int>();
        int totalValue = 0;
        int numChosen = 0;

        foreach (var item in pq) {
            if (numChosen == numWanted) break;
            if (!labelCount.ContainsKey(item.label))
                labelCount[item.label] = 0;
            if (labelCount[item.label] < useLimit) {
                totalValue += item.value;
                labelCount[item.label]++;
                numChosen++;
            }
        }

        return totalValue;
    }

    public static void Main(string[] args) {
        Solution solution = new Solution();
        int[] values = { 5, 4, 3, 2, 1 };
        int[] labels = { 1, 1, 2, 2, 3 };
        int numWanted = 3;
        int useLimit = 1;
        Console.WriteLine("Maximum sum: " + solution.LargestValsFromLabels(values, labels, numWanted, useLimit));
    }
}

This Python implementation uses a priority queue from the heapq library, beginning with negative values to achieve a max-heap. The process continues to extract the maximum value until the constraints are met.

Complexity

Time Complexity: O(n log n) for heap operations.
Space Complexity: O(n) for the heap and label counting.

Try this approach in the editor

Approach 3: Default Approach

TypeScript

function largestValsFromLabels(
    values: number[],
    labels: number[],
    numWanted: number,
    useLimit: number,
): number {
    const n = values.length;
    const pairs = new Array(n);
    for (let i = 0; i < n; ++i) {
        pairs[i] = [values[i], labels[i]];
    }
    pairs.sort((a, b) => b[0] - a[0]);
    const cnt: Map<number, number> = new Map();
    let ans = 0;
    for (let i = 0, num = 0; i < n && num < numWanted; ++i) {
        const [v, l] = pairs[i];
        if ((cnt.get(l) || 0) < useLimit) {
            cnt.set(l, (cnt.get(l) || 0) + 1);
            ++num;
            ans += v;
        }
    }
    return ans;
}

func largestValsFromLabels(values []int, labels []int, numWanted int, useLimit int) (ans int) {
	n := len(values)
	pairs := make([][2]int, n)
	for i := 0; i < n; i++ {
		pairs[i] = [2]int{values[i], labels[i]}
	}
	sort.Slice(pairs, func(i, j int) bool { return pairs[i][0] > pairs[j][0] })
	cnt := map[int]int{}
	for i, num := 0, 0; i < n && num < numWanted; i++ {
		v, l := pairs[i][0], pairs[i][1]
		if cnt[l] < useLimit {
			cnt[l]++
			num++
			ans += v
		}
	}
	return
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Greedy with Sorting	Time Complexity: O(n log n) for sorting the items. Space Complexity: O(n) for storing the tuples and label count dictionary.
Heap-based Greedy Using Priority Queue	Time Complexity: O(n log n) for heap operations. Space Complexity: O(n) for the heap and label counting.
Default Approach	–

Complexity analysis

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.

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.

Largest Values From Labels solution and explanation

The problem

Approach overview

Approach 1: Greedy with Sorting

Approach 2: Heap-based Greedy Using Priority Queue

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Largest Values From Labels solution and explanation

The problem

Approach overview

Approach 1: Greedy with Sorting

Approach 2: Heap-based Greedy Using Priority Queue

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems