Solution: Least Number of Unique Integers after K Removals

Statement

You are given an integer array, arr, and an integer, k. Your task is to remove exactly k elements from the array so that the number of distinct integers remaining in the array is minimized. Determine the minimum possible count of unique integers after the removals.

Constraints:

• $1 \leq$ arr.length $\leq 10^3$

• $1 \leq$ arr[i] $\leq 10^5$

• $0 \leq$ k $\leq$ arr.length

Solution

The solution’s core idea is to reduce the number of unique integers by always removing the least frequent elements first. When we want to minimize the number of unique values remaining after deleting a fixed number of elements, it makes sense to first eliminate those integers that occur less frequently.

This strategy relies on two key observations:

1. We should first target the smallest frequency groups to minimize the remaining unique integers because they require fewer removals to eliminate a whole unique integer.

2. Using a structure that quickly gives us the smallest frequency at each step, such as a min‑heap, allows us to plan quick deletions.

To apply the above intuition, we start by counting how many times each distinct element appears in the array. These counts are placed in a min heap, which lets us access and remove the smallest counts first. Removing numbers that appear the least reduces the variety with minimal deletions, so we repeatedly remove the smallest counts until we use up to k removals. If we reach a count that we can’t fully remove without exceeding k, the remaining heap size plus one gives the number of unique integers left. We stop at that point because any remaining counts directly represent the unique integers left. This approach follows the core intuition by always targeting the most efficient removals first.

Now, let’s look at the solution steps below:

1. Create a frequency map from each integer in arr.

2. Convert all frequency values in map into a min heap, frequencies. This allows instant access to the smallest frequency group at each step.

3. Initialize a counter to $0$ for removals. It keeps track of how many elements we have deleted so far.

4. Next, traverse all frequencies in ascending order and repeatedly:

   1. Remove the smallest frequency from frequencies.

   2. Add that frequency to counter (representing removing all occurrences of that integer).

   3. After each removal, check if counter exceeds k.

      1. If yes, we cannot fully remove that group, so the current heap size plus one gives the count of unique integers left. We return this count as the number of unique integers left after k removals.

5. After traversal, if all frequencies are removed without exceeding k, return $0$, showing that no unique integers are left.

Let’s look at the following illustration to get a better understanding of the solution: