Least Number of Unique Integers after K Removals: Greedy Frequency Pruning

You are given an array of integers arr and an integer k. You can remove exactly k elements from the array. Your goal is to minimize the number of unique integers left after the removals. Return that minimum count.

This is LeetCode 1481: Least Number of Unique Integers after K Removals, a medium problem that combines frequency counting with greedy selection.

For example, given arr = [5, 5, 4, 4, 3] and k = 3, you can remove the single copy of 3 (cost 1) and both copies of 5 (cost 2), spending all 3 removals. Only 4 remains, so the answer is 1.

Why this problem matters

This problem teaches you a pattern that shows up constantly in interviews: reduce a collection to its frequency profile, then make greedy decisions based on those frequencies. You are not choosing which specific elements to remove. You are choosing which groups to eliminate, starting with the cheapest ones.

The same "sort-by-cost-and-pick-greedily" skeleton appears in problems about task scheduling, meeting rooms, and resource allocation. Once you internalize it here, you will recognize it instantly in harder variants.

The key insight

To eliminate a unique integer from the array, you need to remove all of its copies. An element that appears once costs 1 removal. An element that appears five times costs 5. Since you want to eliminate as many unique integers as possible with a fixed budget of k removals, you should always spend your budget on the cheapest elements first.

That is the greedy rule: sort frequencies in ascending order, then subtract each frequency from k until k runs out. Every frequency you can fully subtract is one fewer unique integer in the final answer.

The solution

def findLeastNumOfUniqueInts(arr, k):
    freq = {}
    for x in arr:
        freq[x] = freq.get(x, 0) + 1
    counts = sorted(freq.values())
    removed = 0
    for c in counts:
        if k >= c:
            k -= c
            removed += 1
        else:
            break
    return len(counts) - removed

Visual walkthrough

Here is what each piece does:

1. Build a frequency map from the array. You only care about how many times each value appears, not the values themselves.
2. Extract the frequencies and sort them in ascending order. This puts the cheapest-to-remove elements first.
3. Walk through the sorted frequencies. For each one, check if you have enough k left to remove all copies. If yes, subtract the frequency from k and count it as removed. If no, stop.
4. The answer is the total number of unique values minus however many you fully removed.

Complexity analysis

The sorting step dominates at O(n log n). If you want O(n), you can use bucket sort on the frequencies since every frequency is between 1 and n. For interviews, the sorted version is clean enough and the interviewer is unlikely to push for the bucket sort optimization.

The building blocks

1. Frequency counting with a hash map

The first step is always the same: count how many times each element appears. This reduces the array to its frequency profile, which is the only data you need for the greedy decision.

freq = {}
for x in arr:
    freq[x] = freq.get(x, 0) + 1

You will see this exact pattern in problems like Top K Frequent Elements, Sort Characters by Frequency, and Task Scheduler. The hash map compresses the input into a summary that is easier to reason about.

2. Sort-and-sweep greedy

Once you have a list of costs (frequencies), you sort them and sweep from smallest to largest, spending your budget greedily:

counts = sorted(freq.values())
for c in counts:
    if k >= c:
        k -= c
        removed += 1
    else:
        break

This is the classic "knapsack with uniform weight" pattern. Each item has a cost, you have a fixed budget, and you want to buy as many items as possible. Sorting by cost and buying cheapest-first is provably optimal.

3. Counting survivors

After the greedy sweep, the answer is just the total unique count minus the number you removed. No need to rebuild the array or track which elements survived.

Edge cases

Before submitting, make sure your solution handles these:

• k = 0: you cannot remove anything. The answer is the number of unique elements in the original array.
• k equals the array length: you remove everything. The answer is 0.
• All elements are the same: [7, 7, 7, 7] with any k below 4 means the answer is 1, since you cannot fully eliminate the only element. With k of 4 or more, the answer is 0.
• All elements are unique: [1, 2, 3, 4, 5] with k = 3 means you remove 3 elements (each with freq 1), leaving 2 unique integers.
• k is larger than needed: if k is big enough to remove everything, the answer is 0. The greedy loop naturally handles this because it just keeps subtracting until all frequencies are consumed.
• Single element array: [42] with k = 1 gives 0. With k = 0 gives 1.

From understanding to recall

You have read the solution and it makes sense. Count frequencies, sort them, greedily subtract from k. Three lines of logic. But can you write it from scratch without looking at it?

The details matter: remembering to sort the values of the frequency map (not the keys), knowing to break early when k runs out, and computing the final answer as total minus removed rather than trying to count survivors directly. These are small choices that are easy to mix up under interview pressure.

Spaced repetition closes that gap. You practice writing the frequency-count-and-sweep loop from scratch at increasing intervals. After a few rounds, you see "minimize unique elements after removals" and the code flows out without hesitation.

The greedy frequency pruning pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping they stick.

Related posts

• Top K Frequent Elements - Another frequency counting problem where you extract the top-k elements instead of removing the bottom-k
• Sort Characters by Frequency - Frequency counting followed by reconstruction based on counts
• Task Scheduler - Greedy scheduling where frequency determines the order of operations