Largest Values From Labels

For this medium LC problem, I’m presenting two variations of my solution: Using array and another using PriorityQueue.

The idea behind the solution is the same: To sort all the values in descending order while maintaining the correct mapping of each value to its label. Then we greedily take each of the values while updating the usage map which keeps tracks of how many numbers have we taken so far from each label.

Using Array: Time Complexity O(n)

class Solution {
    public int largestValsFromLabels(int[] values, int[] labels, int num_wanted, int use_limit) {
        final Map<Integer, Integer> usage = new HashMap<>();
        int n = values.length;
        int[][] pairs = new int[n][2];
        
        for(int i=0; i < n; i++){
            pairs[i][0] = values[i];
            pairs[i][1] = labels[i];
            usage.put(labels[i], use_limit);
        }
        
        Arrays.sort(pairs, (a, b) -> b[0] - a[0]);

        int sum = 0;
        for(int i=0; i < n; i++){
            int value = pairs[i][0];
            int label = pairs[i][1];
            
            if(usage.get(label) > 0 && num_wanted > 0){
                usage.put(label, usage.get(label) - 1);
                sum += value;
                num_wanted--;
            }
        }
        
        return sum;
    }
}

Runtime: 17 ms, faster than 77.42% of Java online submissions for Largest Values From Labels.
Memory Usage: 42.9 MB, less than 100.00% of Java online submissions for Largest Values From Labels.

Using Priority Queue: Time Complexity O(nlogn)

class Solution {
    public int largestValsFromLabels(int[] values, int[] labels, int num_wanted, int use_limit) {
        final Map<Integer, Integer> usage = new HashMap<>();
        int n = values.length;
        final PriorityQueue<int[]> mapping = new PriorityQueue<>((a,b) -> b[1] - a[1]);
        
        for(int i=0; i < n; i++){
            mapping.add(new int[]{labels[i], values[i]});
            usage.put(labels[i], use_limit);
        }
        
        int sum = 0;
        
        while(!mapping.isEmpty()){
            int[] pair = mapping.poll();
            if(usage.get(pair[0]) > 0 && num_wanted > 0){
                usage.put(pair[0], usage.get(pair[0]) - 1);
                sum += pair[1];
                num_wanted--;
            }
        }
        
        return sum;
    }
}

Runtime: 21 ms, faster than 52.79% of Java online submissions for Largest Values From Labels.
Memory Usage: 42.8 MB, less than 100.00% of Java online submissions for Largest Values From Labels.

Marc Lester Tan

Using Array: Time Complexity O(n)

Using Priority Queue: Time Complexity O(nlogn)