Least Number of Unique Integers after K Removals

medium array hash map greedy sorting counting

Problem

Given arr and k, return the least number of unique integers left in the array after removing exactly k elements.

Inputarr=[4,3,1,1,3,3,2], k=3

Output2

Remove all 4 and 2 (cost 1+1=2), then one more 1 → uniques {1,3} remain.

arr

from collections import Counter
def find_least_num_of_unique_ints(arr, k):
    freq = sorted(Counter(arr).values())
    uniques = len(freq)
    for c in freq:
        if k >= c: k -= c; uniques -= 1
        else: break
    return uniques

function findLeastNumOfUniqueInts(arr, k) {
  const f = {}; for (const x of arr) f[x] = (f[x] || 0) + 1;
  const freq = Object.values(f).sort((a, b) => a - b);
  let u = freq.length;
  for (const c of freq) {
    if (k >= c) { k -= c; u--; } else break;
  }
  return u;
}

class Solution {
    public int findLeastNumOfUniqueInts(int[] arr, int k) {
        Map f = new HashMap<>();
        for (int x : arr) f.merge(x, 1, Integer::sum);
        List freq = new ArrayList<>(f.values());
        Collections.sort(freq);
        int u = freq.size();
        for (int c : freq) { if (k >= c) { k -= c; u--; } else break; }
        return u;
    }
}

int findLeastNumOfUniqueInts(vector& arr, int k) {
    unordered_map f;
    for (int x : arr) f[x]++;
    vector freq;
    for (auto& p : f) freq.push_back(p.second);
    sort(freq.begin(), freq.end());
    int u = freq.size();
    for (int c : freq) { if (k >= c) { k -= c; u--; } else break; }
    return u;
}

Explanation

To leave the fewest distinct values, we should fully erase whole values whenever we can. Wiping out a value that appears only once costs just 1 removal, while a value appearing many times costs many removals. So the greedy move is to eliminate the rarest values first.

We count how often each value appears, then take just the list of counts and sort it ascending. Smaller counts come first, meaning the cheapest values to remove are at the front.

We walk that sorted list spending our budget k. For each count c, if k >= c we can fully delete that value: subtract c from k and drop the unique count by one. The first time k is too small to finish a value, we stop — that value survives.

Example: arr=[4,3,1,1,3,3,2], k=3. Counts are 4:1, 2:1, 1:2, 3:3, sorted as [1, 1, 2, 3]. Spend 1 on a value (k=2), 1 more on another (k=1), then we cannot afford the count-2 value, so 2 unique values remain.

The sort is what makes this O(n log n); everything else is a single pass.

Time: O(n log n) Space: O(n)