Least Number of Unique Integers after K Removals

How it works

Since frequencies are bounded by the array length, we can use bucket sort to avoid comparison-based sorting. We create buckets where bucket f contains the count of integers with frequency f. Then we iterate through buckets from frequency 1 upward, removing as many complete integers as possible at each frequency level.

Steps

1. Build a frequency map of all integers.
2. Create a frequency list (bucket array) where freqList[f] counts how many integers have frequency f.
3. Iterate f from 1 to the array length:
   • Calculate how many integers with frequency f can be fully removed given the remaining k.
   • Subtract the cost from k and reduce the result count.
   • If k cannot remove all integers at this frequency, compute partial removal and break.
4. Return the remaining unique count.

Complexity

• Time complexity: O(n)
• Space complexity: O(n)

Things to watch for

Removing High-Frequency Elements First

The greedy strategy requires removing elements with the lowest frequency first to maximize the reduction in unique count. Removing high-frequency elements wastes removals since you need more deletions to eliminate a single unique integer. Always sort frequencies in ascending order.

Counting Unique Integers Incorrectly

A subtle bug is decrementing the unique count even when you cannot fully remove all occurrences of an integer. If k is less than the current frequency, you cannot eliminate that unique integer, so the count should not decrease. Only reduce the unique count when all occurrences are removed.

Forgetting Partial Removal Logic

When k cannot fully cover the current frequency but can partially cover it, some implementations incorrectly skip this case entirely. While partial removal does not reduce the unique count, you still need to account for it when moving to the next frequency bucket in bucket sort approaches.

from typing import List
from collections import Counter

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        freq = Counter(arr)
        freq_list = [0] * (len(arr) + 1)

        for n, f in freq.items():
            freq_list[f] += 1

        res = len(freq)
        for f in range(1, len(freq_list)):
            remove = freq_list[f]
            if k >= f * remove:
                k -= f * remove
                res -= remove
            else:
                remove = k // f
                res -= remove
                break
        return res

class Solution {
public:
    int findLeastNumOfUniqueInts(vector<int>& arr, int k) {
        unordered_map<int, int> freqMap;
        for (int num : arr) {
            freqMap[num]++;
        }

        vector<int> freqList(arr.size() + 1, 0);
        for (auto& [_, f] : freqMap) {
            freqList[f]++;
        }

        int res = freqMap.size();
        for (int f = 1; f < freqList.size(); f++) {
            int remove = freqList[f];
            if (k >= f * remove) {
                k -= f * remove;
                res -= remove;
            } else {
                remove = k / f;
                res -= remove;
                break;
            }
        }
        return res;
    }
};