Problem statement

https://leetcode.com/problems/largest-values-from-labels/

Solution

We sort items by value and try to choose the most valueable one. We keep how much we take in total as well how much we taken of each type.

Complexity

It is O(n log n) for time and space.

Code

class Solution:
    def largestValsFromLabels(self, values, labels, numWanted, useLimit):
        arr = sorted([(x, y) for x, y in zip(values, labels)])[::-1]
        taken_types = Counter()
        ans = 0
        for x, y in arr:
            if numWanted == 0: break
            if taken_types[y] >= useLimit: continue
            ans += x
            taken_types[y] += 1
            numWanted -= 1
            
        return ans