LeetCode Entry
1481. Least Number of Unique Integers after K Removals
Min uniq count after removing k numbers.
1481. Least Number of Unique Integers after K Removals medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/507
Problem TLDR
Min uniq count after removing k numbers.
Intuition
Just to be sure what the problem is about, let’s write some other examples: [1,2,3,4,4] k = 3, [1,2,3,4,4,4] k = 3, [1,2,3,3,4,4,4] k = 3. The first two will give the same unswer 1, the last one is 2, however. As soon as we understood the problem, just implement the algorithm: sort numbers by frequency and remove from smallest to the largest.
Approach
Let’s try to make the code shorter, by using languages:
- Kotlin:
asList,groupingBy,eachCount,sorted,run - Rust:
entry+or_insert,Vec::from_iter,into_values,sort_unstable,fold
Complexity
-
Time complexity: \(O(nlog(n))\), worst case, all numbers are uniq
-
Space complexity: \(O(n)\)
Code
fun findLeastNumOfUniqueInts(arr: IntArray, k: Int) = arr
.asList().groupingBy { it }.eachCount()
.values.sorted().run {
var c = k
size - count { c >= it.also { c -= it } }
}
pub fn find_least_num_of_unique_ints(arr: Vec<i32>, mut k: i32) -> i32 {
let mut freq = HashMap::new();
for x in arr { *freq.entry(x).or_insert(0) += 1 }
let mut freq = Vec::from_iter(freq.into_values());
freq.sort_unstable();
freq.iter().fold(freq.len() as i32, |acc, count| {
k -= count;
if k < 0 { acc } else { acc - 1 }
})
}