Least Number of Unique Integers after K Removals - Video Solutions

Problem Overview: You receive an integer array and an integer k. Remove exactly k elements so the number of distinct integers left in the array is as small as possible. The key observation: removing numbers that appear fewer times eliminates unique values faster than removing frequent numbers.

Approach 1: Frequency Count + Min-Heap (O(n + m log m) time, O(m) space)

Start by counting how many times each value appears using a hash map. This transforms the problem into managing frequencies instead of raw elements. Push all frequencies into a min-heap so the smallest counts come first. Repeatedly pop the smallest frequency and subtract it from k. If k is large enough to remove all occurrences of that number, you eliminate one unique integer. Continue until k is exhausted. The heap ensures you always remove the cheapest unique number first. Time complexity is O(n + m log m) where m is the number of distinct integers, and space complexity is O(m). This approach combines hash table counting with a priority queue for optimal removal order.

Approach 2: Greedy Frequency Counting with Sorting (O(n + m log m) time, O(m) space)

Instead of a heap, store the frequency counts in a list and sort them in ascending order. This produces the same removal order as the heap but uses sorting once instead of repeated heap operations. Iterate through the sorted frequencies. For each frequency f, check if k ≥ f. If true, remove all occurrences and reduce k by f, which eliminates one unique number. Once k becomes smaller than the next frequency, you stop because removing that number completely is impossible. The remaining count of frequencies gives the number of unique integers left. This greedy strategy works because removing smaller groups always yields the maximum reduction in unique values. Complexity is O(n + m log m) time and O(m) space due to the frequency map and sorting. This technique highlights classic greedy reasoning combined with sorting.

Recommended for interviews: The greedy frequency approach is what most interviewers expect. Building a frequency map and removing the smallest counts first demonstrates a clear understanding of greedy optimization. The min-heap solution shows stronger familiarity with priority queues and dynamic selection, while the sorted-frequency approach is simpler and often easier to implement quickly during interviews.