Least Number of Unique Integers after K Removals

Given an array of integers arr and an integer k. Find the least number of unique integers after removing exactly k elements.

Example 1:

Input: arr = [5,5,4], k = 1
Output: 1
Explanation: Remove the single 4, only 5 is left.

Example 2:

Input: arr = [4,3,1,1,3,3,2], k = 3
Output: 2
Explanation: Remove 4, 2 and either one of the two 1s or three 3s. 1 and 3 will be left.

Constraints:

• 1 <= arr.length <= 10^5

• 1 <= arr[i] <= 10^9

• 0 <= k <= arr.length

class Solution {
    public int findLeastNumOfUniqueInts(int[] arr, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        int max = 0;
        int count = 0;
        for (int x : arr) {
            if (!map.containsKey(x)) {
                map.put(x, 1);
                count++;
            } else
                map.put(x, map.get(x) + 1);
            max = Math.max(max, map.get(x));
        }
        List<Integer>[] freq = new ArrayList[max + 1];
        for (int i = 0; i <= max; i++)
            freq[i] = new ArrayList<>();
        for (int x : map.keySet())
            freq[map.get(x)].add(x);
        int removed = 0, pointer = 1;
        // Start removing the lowest frequency number to remove max unique digits
        // This will result in min answer
        while (removed < k) {
            if (freq[pointer].size() > 0) {
                // If we can remove all the difits with this frequency
                if (removed + pointer * freq[pointer].size() <= k) {
                    count -= freq[pointer].size();
                    removed += pointer * freq[pointer].size();
                }
                // else we will remove what we can
                else {
                    int possible = (k - removed) / pointer;
                    removed = k;
                    count -= possible;
                }
            }
            pointer++;
        }
        return count;
    }
}