1481. Least Number of Unique Integers after K Removals

HashMap + Sort

T: O(n + mlogm + k), n is arr length. m is the number of key in hashmap
S: O(n + m)

```java
class Solution {
    public int findLeastNumOfUniqueInts(int[] arr, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : arr) {
            freq.put(num, freq.getOrDefault(num, 0)+1);
        }
        List<Integer> list = new ArrayList<>(freq.keySet());
        Collections.sort(list, (a, b) -> freq.get(a) - freq.get(b));

        for (int i = 0; i < list.size() && k > 0; i++) {
            int key = list.get(i);
            int count = freq.get(key);
            while (count > 0) {
                count--;
                if (count == 0) {
                    freq.remove(key);
                }
                k--;
                if (k == 0) {
                    return freq.size();
                }
            }
        }
        return freq.size();
    }
}

/**
T: O(n + mlogm + k), n is arr length. m is the number of key in hashmap
S: O(n + m)

 */
```

HashMap + bucket sort

because freq at most is arr.length... so we can create a bucket array to sort the count

T: O(n)
S: O(n)

```java
class Solution {
    public int findLeastNumOfUniqueInts(int[] arr, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : arr) {
            freq.put(num, freq.getOrDefault(num, 0)+1);
        }
        if (k == 0) {
            return freq.size();
        }

        int[] bucket = new int[arr.length+1];
        for (int count : freq.values()) { 
            // bucket and freq -> [4,3,1,1,3,3,2] -> bucket[0, 2, 1, 1, 0, 0, 0], k = 3, 
            // so -> [0, 0, 1, 1, 0, 0, 0] -> count = 2 (2 kind of number) 
            bucket[count]++;
        }
        for (int i = 0; i < bucket.length && k > 0; i++) {
            while (bucket[i] > 0) {
                int freqVal = i;
                if (k >= freqVal) {
                    bucket[i]--;
                    k -= freqVal;
                } else {
                    k = 0;
                }
                if (k == 0) {
                    break;
                }
            }
        }
        int count = 0;
        for (int i = 0; i < bucket.length; i++) {
            if (bucket[i] > 0) {
                count += bucket[i];
            }
        }
        return count;
    }
}

/**
T: O(n)
S: O(n)

 */
```