We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Largest Values From Labels

Number: 1169

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given two arrays, one containing item values and the other containing their corresponding labels, along with two integers numWanted and useLimit, the goal is to select at most numWanted items such that no label is used more than useLimit times. The objective is to maximize the sum of the selected item values.

Key Insights

  • Sort the items in descending order based on their values to always consider the highest available value first.
  • Use a hash table (or dictionary) to keep track of how many times each label has been used.
  • Choose items greedily from the sorted order while respecting the label useLimit.
  • Stop the selection either when the numWanted items are chosen or no further valid items exist.

Space and Time Complexity

Time Complexity: O(n log n) due to the sorting step, where n is the number of items. Space Complexity: O(n) for storing the item-value pairs and the label count mapping.

Solution

The solution starts by pairing each value with its corresponding label. These pairs are then sorted in descending order based on the values. A hash table (or dictionary) is used to count how many times each label has been selected. We iterate over the sorted item pairs and if the current label has been used less than useLimit times, add the item’s value to the running sum and increment the label count. Continue until we have either selected numWanted items or exhaust the list. This greedy approach ensures that we achieve the maximum sum while adhering to the constraints.

Code Solutions

# Python solution with line-by-line comments
from collections import defaultdict
from typing import List

class Solution:
    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:
        # Pair each item with its corresponding label
        items = list(zip(values, labels))
        # Sort the items in descending order based on value
        items.sort(key=lambda x: x[0], reverse=True)
        
        # Dictionary to count how many times a label has been used
        label_count = defaultdict(int)
        total_sum = 0  # Sum of selected item values
        count = 0      # Number of items selected so far
        
        # Iterate over each item in the sorted list
        for value, label in items:
            # Check if the current label can still be used
            if label_count[label] < useLimit:
                total_sum += value    # Add the value of the item
                label_count[label] += 1  # Increment usage count for this label
                count += 1  # Increment count of selected items
                # If we have reached the numWanted limit, break out of the loop
                if count == numWanted:
                    break
        return total_sum
← Back to All Questions