1090. Largest Values From Labels LeetCode Solution

In this guide, you will get 1090. Largest Values From Labels LeetCode Solution with the best time and space complexity. The solution to Largest Values From Labels problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Largest Values From Labels solution in C++
Largest Values From Labels solution in Java
Largest Values From Labels solution in Python
Additional Resources

1090. Largest Values From Labels LeetCode Solution image

Problem Statement of Largest Values From Labels

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

Complexity Analysis

Time Complexity: O(\texttt{sort})
Space Complexity: O(n)

1090. Largest Values From Labels LeetCode Solution in C++

class Solution {
 public:
  int largestValsFromLabels(vector<int>& values, vector<int>& labels,
                            int numWanted, int useLimit) {
    const int n = values.size();
    int ans = 0;
    vector<pair<int, int>> items;
    unordered_map<int, int> labelsUsed;

    for (int i = 0; i < n; ++i)
      items.emplace_back(values[i], labels[i]);

    ranges::sort(items, ranges::greater{},
                 [](const pair<int, int>& item) { return item.first; });

    for (const auto& [value, label] : items)
      if (labelsUsed[label] < useLimit) {
        ans += value;
        ++labelsUsed[label];
        if (--numWanted == 0)
          break;
      }

    return ans;
  }
};
/* code provided by PROGIEZ */