Least number of unique integers after k removals

Array Hash Table Greedy Sorting Counting

63.7% acceptance

Feb 25, 2026

2338

234

Given an array of integers arr and an integer k. Find the least number of unique integers after removing exactly k elements.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

use std::collections::HashMap;

impl Solution {
  pub fn find_least_num_of_unique_ints(arr: Vec<i32>, k: i32) -> i32 {
    let mut freq: HashMap<i32, i32> = HashMap::new();
    for &x in &arr { *freq.entry(x).or_insert(0) += 1; }
    let mut counts: Vec<i32> = freq.values().copied().collect();
    counts.sort_unstable();
    let mut remaining = k;
    let mut unique = counts.len() as i32;
    for c in counts {
      if remaining >= c { remaining -= c; unique -= 1; }
      else { break; }
    }
    unique
  }
}