Skip to content

1481. Least Number of Unique Integers after K Removals 👍

  • Time: $O(n\log n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  int findLeastNumOfUniqueInts(vector<int>& arr, int k) {
    unordered_map<int, int> count;
    priority_queue<int, vector<int>, greater<>> minHeap;

    for (const int a : arr)
      ++count[a];

    for (const auto& [_, freq] : count)
      minHeap.push(freq);

    // Greedily remove the k least frequent numbers to have the least number of
    // unique integers.
    while (k > 0)
      k -= minHeap.top(), minHeap.pop();

    return minHeap.size() + (k < 0 ? 1 : 0);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
  public int findLeastNumOfUniqueInts(int[] arr, int k) {
    Map<Integer, Integer> count = new HashMap<>();

    for (final int a : arr)
      count.merge(a, 1, Integer::sum);

    Queue<Integer> minHeap = new PriorityQueue<>(count.values());

    // Greedily remove the k least frequent numbers to have the least number of unique integers.
    while (k > 0)
      k -= minHeap.poll();

    return minHeap.size() + (k < 0 ? 1 : 0);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
  def findLeastNumOfUniqueInts(self, arr: list[int], k: int) -> int:
    minHeap = list(collections.Counter(arr).values())
    heapq.heapify(minHeap)

    # Greedily remove the k least frequent numbers to have the least number of unique integers.
    while k > 0:
      k -= heapq.heappop(minHeap)

    return len(minHeap) + (1 if k < 0 else 0)