Welcome to Subscribe On Youtube

1090. Largest Values From Labels

Description

There is a set of n items. You are given two integer arrays values and labels where the value and the label of the ith element are values[i] and labels[i] respectively. You are also given two integers numWanted and useLimit.

Choose a subset s of the n elements such that:

• The size of the subset s is less than or equal to numWanted.
• There are at most useLimit items with the same label in s.

The score of a subset is the sum of the values in the subset.

Return the maximum score of a subset s.

 

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.

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.

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.

 

Constraints:

• n == values.length == labels.length
• 1 <= n <= 2 * 104
• 0 <= values[i], labels[i] <= 2 * 104
• 1 <= numWanted, useLimit <= n

Solutions

• Java
• C++
• Python
• Go
• TypeScript

• class Solution {
      public int largestValsFromLabels(int[] values, int[] labels, int numWanted, int useLimit) {
          int n = values.length;
          int[][] pairs = new int[n][2];
          for (int i = 0; i < n; ++i) {
              pairs[i] = new int[] {values[i], labels[i]};
          }
          Arrays.sort(pairs, (a, b) -> b[0] - a[0]);
          Map<Integer, Integer> cnt = new HashMap<>();
          int ans = 0, num = 0;
          for (int i = 0; i < n && num < numWanted; ++i) {
              int v = pairs[i][0], l = pairs[i][1];
              if (cnt.getOrDefault(l, 0) < useLimit) {
                  cnt.merge(l, 1, Integer::sum);
                  num += 1;
                  ans += v;
              }
          }
          return ans;
      }
  }
  

• class Solution {
  public:
      int largestValsFromLabels(vector<int>& values, vector<int>& labels, int numWanted, int useLimit) {
          int n = values.size();
          vector<pair<int, int>> pairs(n);
          for (int i = 0; i < n; ++i) {
              pairs[i] = {-values[i], labels[i]};
          }
          sort(pairs.begin(), pairs.end());
          unordered_map<int, int> cnt;
          int ans = 0, num = 0;
          for (int i = 0; i < n && num < numWanted; ++i) {
              int v = -pairs[i].first, l = pairs[i].second;
              if (cnt[l] < useLimit) {
                  ++cnt[l];
                  ++num;
                  ans += v;
              }
          }
          return ans;
      }
  };
  

• class Solution:
      def largestValsFromLabels(
          self, values: List[int], labels: List[int], numWanted: int, useLimit: int
      ) -> int:
          ans = num = 0
          cnt = Counter()
          for v, l in sorted(zip(values, labels), reverse=True):
              if cnt[l] < useLimit:
                  cnt[l] += 1
                  num += 1
                  ans += v
                  if num == numWanted:
                      break
          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
  }
  

• 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;
  }
  
  

All Problems

All Solutions