1169. Largest Values From Labels¶

Difficulty: Medium

1169. Largest Values From Labels

Medium

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 * 10⁴
0 <= values[i], labels[i] <= 2 * 10⁴
1 <= numWanted, useLimit <= n

Solution¶

class Solution {
    static class Pair {
        int first, second;
        public Pair(int first, int second) {
            this.first = first;
            this.second = second;
        }
        @Override
        public String toString() {
            return "(" + first + " " + second + ")";
        }
    }
    static class custom_sort implements Comparator<Pair> {
        @Override
        public int compare(Pair first, Pair second) {
            return Integer.compare(second.first, first.first);
        }
    }
    public int largestValsFromLabels(int[] values, int[] labels, int numWanted, int useLimit) {
        int n = values.length;
        ArrayList<Pair> res = new ArrayList<>(); 
        for (int i = 0; i < n; i++) res.add(new Pair(values[i], labels[i]));
        Collections.sort(res, new custom_sort());
        int sum = 0, count = 0;
        int freq[] = new int[(int)(1e5 + 1)];
        for (int i = 0; i < n; i++) {
            if (count == numWanted) break;
            Pair current = res.get(i);
            if (freq[current.second] == useLimit) continue;
            sum += current.first;
            count++;
            freq[current.second]++;
        }
        return sum;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here