Leetcode 1481: Least Number of Unique Integers after K Removals

In this Leetcode problem, we try to remove the maximum number of unique integers in an array.

Problem statement

Solution

A couple of ideas for the solution:

1. We want to remove the number that appear the least number of times first. That’s the most efficient way of removing the maximum of unique integers.
2. To do that we want to build the map countToNumValues, which for each count key gives the number of unique integers that appear exactly count times in the array
3. To build countToNumValues we use the intermediary map valueToCount, which give for each value in the array the number of times it appears in the array
4. countToNumValues is a TreeMap, which means the keys are sorted, as we want to tackle the integer with 1, 2, 3 counts in order
5. We keep track of leftover the number of integers we can still remove
6. When we run out of integers to remove, we add the remaining number to res, and return res in the end.

class Solution {
    public int findLeastNumOfUniqueInts(int[] arr, int k) {
        Map<Integer, Integer> valueToCount = new HashMap<>();
        for (int v : arr) {
            valueToCount.put(
                v, valueToCount.getOrDefault(v, 0) +…