Find the Largest Values From Labels
Given two arrays values[] and labels[] of size n, where values[i] represents the value of the ith item and labels[i] represents the label of the ith item. Additionally, there are two integers numNeeded and limit.
The task is to choose a subset s of the n elements such that:
- The size of the subset s is less than or equal to numNeeded.
- There are at most limit items with the same label in s.
The score of a subset is the sum of the values of the elements in the subset. The goal is to return the maximum score of a subset s that satisfies the above conditions.
Example:
Input: values = [5,4,3,2,1], labels = [1,1,2,2,3], numNeeded = 3, limit = 1
Output: 9
Explanation: The subset chosen is the first, third, and fifth items.Input: values = [5,4,3,2,1], labels = [1,3,3,3,2], numNeeded = 3, limit = 2
Output: 12
Explanation: The subset chosen is the first, second, and third items.
Approach:
The given problem involves selecting a subset of values from the values vector, with the maximum size restricted by numNeeded. Initially, without considering the limit, we could simply choose the top numNeeded values from the values array. However, the introduction of the limit constraint complicates the selection process.
To adapt to this constraint, we must keep track of how many values of each label we have already selected. If the usage limit for a particular label is reached, we are forced to switch to selecting values with different labels. This adds complexity to the selection process, as we must carefully manage the balance between maximizing the overall value and adhering to the usage limits for each label.
Steps-by-step approach:
- First, we combine each value with its corresponding label and store them as pairs in a 2D array arr[][].
- Sort the arr[][] based on the values in non-decreasing order.
- Starting from the end of the sorted arr[][], we iterate over each element.
- For each element, if there are still values remaining to be selected (numNeeded > 0) and the usage limit for the label corresponding to the current element is not exceeded (mp[arr[i][1]] < limit), we select the value, increment the usage count for the label, and decrement numNeeded.
- Finally, return the total score, which represents the sum of the selected values.
Below is the implementation of the above approach:
#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
// Function to find the largest sum of values with label
// constraints
int largestValsFromLabels(vector<int>& values,
vector<int>& labels,
int numWanted, int useLimit)
{
int n = values.size();
// Create a combined vector where each element is a pair
// of (value, label)
vector<vector<int> > arr;
for (int i = 0; i < n; ++i) {
arr.push_back({ values[i], labels[i] });
}
// Sort the combined vector by value in descending order
sort(arr.rbegin(), arr.rend());
// Map to store label counts (used to enforce useLimit)
unordered_map<int, int> mp;
int score = 0;
// Iterate through sorted values, prioritizing labels
// within their use limit
for (int i = 0; i < n && numWanted > 0; ++i) {
int value = arr[i][0];
int label = arr[i][1];
// If we can still pick values from this label and
// haven't reached the limit
if (mp[label] < useLimit) {
mp[label]++;
score += value;
numWanted--;
}
}
return score;
}
int main()
{
vector<int> values = { 5, 4, 3, 2, 1 };
vector<int> labels = { 1, 1, 2, 2, 3 };
int numWanted = 3;
int useLimit = 1;
int largest_sum = largestValsFromLabels(
values, labels, numWanted, useLimit);
cout << "The largest sum of values with label "
"constraints is: "
<< largest_sum << endl;
return 0;
}
import java.util.*;
public class Main {
// Function to find the largest sum of values with label
// constraints
public static int
largestValsFromLabels(List<Integer> values,
List<Integer> labels,
int numWanted, int useLimit)
{
int n = values.size();
// Create a combined list where each element is a
// pair of (value, label)
List<int[]> arr = new ArrayList<>();
for (int i = 0; i < n; ++i) {
arr.add(
new int[] { values.get(i), labels.get(i) });
}
// Sort the combined list by value in descending
// order
arr.sort((a, b) -> Integer.compare(b[0], a[0]));
// Map to store label counts (used to enforce
// useLimit)
Map<Integer, Integer> mp = new HashMap<>();
int score = 0;
// Iterate through sorted values, prioritizing
// labels within their use limit
for (int i = 0; i < n && numWanted > 0; ++i) {
int value = arr.get(i)[0];
int label = arr.get(i)[1];
// If we can still pick values from this label
// and haven't reached the limit
if (mp.getOrDefault(label, 0) < useLimit) {
mp.put(label,
mp.getOrDefault(label, 0) + 1);
score += value;
numWanted--;
}
}
return score;
}
public static void main(String[] args)
{
List<Integer> values = Arrays.asList(5, 4, 3, 2, 1);
List<Integer> labels = Arrays.asList(1, 1, 2, 2, 3);
int numWanted = 3;
int useLimit = 1;
int largestSum = largestValsFromLabels(
values, labels, numWanted, useLimit);
System.out.println(
"The largest sum of values with label constraints is: "
+ largestSum);
}
}
// This code is contributed by Shivam
from typing import List
from collections import defaultdict
def largestValsFromLabels(values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:
n = len(values)
# Create a combined list of tuples (value, label)
arr = [(values[i], labels[i]) for i in range(n)]
# Sort the combined list by value in descending order
arr.sort(reverse=True, key=lambda x: x[0])
# Dictionary to store label counts (used to enforce useLimit)
label_count = defaultdict(int)
score = 0
# Iterate through sorted values, prioritizing labels within their use limit
for value, label in arr:
if numWanted <= 0:
break
# If we can still pick values from this label and haven't reached the limit
if label_count[label] < useLimit:
label_count[label] += 1
score += value
numWanted -= 1
return score
values = [5, 4, 3, 2, 1]
labels = [1, 1, 2, 2, 3]
numWanted = 3
useLimit = 1
largest_sum = largestValsFromLabels(values, labels, numWanted, useLimit)
print(f'The largest sum of values with label constraints is: {largest_sum}')
# This code is contributed by Susobhan Akhuli
function largestValsFromLabels(values, labels, numWanted, useLimit) {
const n = values.length;
// Create an array of pairs (value, label)
let arr = [];
for (let i = 0; i < n; ++i) {
arr.push([values[i], labels[i]]);
}
// Sort the array by value in descending order
arr.sort((a, b) => b[0] - a[0]);
// Map to store label counts (used to enforce useLimit)
let labelCount = new Map();
let score = 0;
// Iterate through sorted values, prioritizing labels within their use limit
for (let i = 0; i < n && numWanted > 0; ++i) {
let value = arr[i][0];
let label = arr[i][1];
// If we can still pick values from this label and haven't reached the limit
if ((labelCount.get(label) || 0) < useLimit) {
labelCount.set(label, (labelCount.get(label) || 0) + 1);
score += value;
numWanted--;
}
}
return score;
}
function main() {
let values = [5, 4, 3, 2, 1];
let labels = [1, 1, 2, 2, 3];
let numWanted = 3;
let useLimit = 1;
let largestSum = largestValsFromLabels(values, labels, numWanted, useLimit);
console.log("The largest sum of values with label constraints is: " + largestSum);
}
// Call the main function to execute the code
main();
Output
The largest sum of values with label constraints is: 9
Time complexity: O(n log n).
- Let n be the size of the values vector.
- Combining values and labels takes O(n) time. Sorting the arr vector takes O(n log n) time. The greedy selection process also takes O(n) time.
- Thus, the overall time complexity of the solution is O(n log n).
Auxiliary Space: O(n) to store the arr vector and the unordered map mp
Contact Us