1481. Least Number of Unique Integers after K Removals LeetCode Solution

In this guide, you will get 1481. Least Number of Unique Integers after K Removals LeetCode Solution with the best time and space complexity. The solution to Least Number of Unique Integers after K Removals problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Least Number of Unique Integers after K Removals solution in C++
Least Number of Unique Integers after K Removals solution in Java
Least Number of Unique Integers after K Removals solution in Python
Additional Resources

1481. Least Number of Unique Integers after K Removals LeetCode Solution image

Problem Statement of 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

Complexity Analysis

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

1481. Least Number of Unique Integers after K Removals LeetCode Solution in C++

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);
  }
};
/* code provided by PROGIEZ */

1481. Least Number of Unique Integers after K Removals LeetCode Solution in Java

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);
  }
}
// code provided by PROGIEZ

1481. Least Number of Unique Integers after K Removals LeetCode Solution in Python

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)
 # code by PROGIEZ