Least Number of Unique Integers after K Removals — Solution
Least Number of Unique Integers after K Removals solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Least Number of Unique Integers after K Removals is a medium coding problem on arrays, hash table and greedy.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Greedy, Heap
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an integer array arr and an integer k, remove exactly k elements so that the number of distinct values remaining is as small as possible, and return that count.
Example 1
Input: arr = [5,5,4], k = 1
Output: 1
Explanation: Remove the 4; only 5 remains.
Example 2
Input: arr = [4,3,1,1,3,3,2], k = 3
Output: 2
Explanation: Remove 4, 2 and one 1.
Constraints
1 <= arr.length <= 301 <= arr[i] <= 500 <= k <= arr.length
Hints for Least Number of Unique Integers after K Removals
Hint 1
Eliminate the rarest values first — they cost the fewest removals.
Hint 2
Sort the frequency counts ascending and consume k greedily.
How to solve Least Number of Unique Integers after K Removals
Removing a value entirely costs exactly as many deletions as its frequency, and removing only some copies of a value buys you nothing — the value still counts as distinct. So the whole problem is: with a budget of k, eliminate as many values as possible, and the cheapest values to eliminate are the rarest ones.
Approach
- Count how many times each value occurs.
- Collect the frequencies and sort them ascending.
- Walk them from smallest to largest, spending
kon each frequency you can afford in full and decrementing the count of distinct values. - Stop at the first frequency you cannot pay for — everything after it is at least as expensive.
- Return the number of distinct values still standing.
Why it works
This is a classic exchange argument. Take any optimal solution that eliminates a set of values; if it skips a cheaper value in favour of a dearer one, swapping them keeps the same number of values eliminated and frees budget, so it is no worse. Repeating the swap turns any optimum into the greedy "cheapest first" order — so greedy is optimal. Partial removals are provably wasted, because spending on copies without finishing a value does not reduce the distinct count.
Complexity
- Time —
O(n + d log d) - Space —
O(d)
Pitfalls
- You must be able to afford a frequency in full before eliminating it; a partial spend does not reduce the answer and just wastes budget.
- Sort the frequencies ascending, not the values.
kmay be0, and it may be large enough to remove everything — both must fall out of the loop naturally.- Break out of the loop at the first unaffordable frequency; continuing to scan can wrongly skip past it to a coincidentally cheaper one (there isn't one once sorted, but the logic must not rely on that).
Reference solution
Python
from typing import List
from collections import Counter
def findLeastNumOfUniqueInts(arr: List[int], k: int) -> int:
freqs = sorted(Counter(arr).values())
remaining = len(freqs)
for f in freqs:
if k >= f:
k -= f
remaining -= 1
else:
break
return remainingJava
public static int findLeastNumOfUniqueInts(int[] arr, int k) {
Map<Integer, Integer> count = new HashMap<>();
for (int x : arr) count.put(x, count.getOrDefault(x, 0) + 1);
List<Integer> freqs = new ArrayList<>(count.values());
Collections.sort(freqs);
int remaining = freqs.size();
int budget = k;
for (int f : freqs) {
if (budget >= f) {
budget -= f;
remaining--;
} else {
break;
}
}
return remaining;
}C++
int findLeastNumOfUniqueInts(vector<int>& arr, int k) {
map<int, int> count;
for (int x : arr) count[x]++;
vector<int> freqs;
for (const auto& e : count) freqs.push_back(e.second);
sort(freqs.begin(), freqs.end());
int remaining = (int) freqs.size();
int budget = k;
for (int f : freqs) {
if (budget >= f) {
budget -= f;
remaining--;
} else {
break;
}
}
return remaining;
}JavaScript
var findLeastNumOfUniqueInts = function(arr, k) {
const count = new Map();
for (const x of arr) count.set(x, (count.get(x) || 0) + 1);
const freqs = Array.from(count.values()).sort(function(a, b) { return a - b; });
let remaining = freqs.length;
for (const f of freqs) {
if (k >= f) {
k -= f;
remaining--;
} else {
break;
}
}
return remaining;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets