Minimum number of groups to create a valid assignment

Array Hash Table Greedy

24.8% acceptance

Feb 25, 2026

395

188

You are given a collection of numbered balls and instructed to sort them into boxes for a nearly balanced distribution. There are two rules you must follow: Balls with the same box must have the same value. But, if you have more than one ball with the same number, you can put them in different boxes. The biggest box can only have one more ball than the smallest box. Return the fewest number of boxes to sort these balls following these rules.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_groups_for_valid_assignment(balls: Vec<i32>) -> i32 {
    let mut freq = std::collections::HashMap::<i32, usize>::new();
    for &b in &balls {
      *freq.entry(b).or_default() += 1;
    }
    let freqs: Vec<usize> = freq.values().cloned().collect();
    let min_freq = *freqs.iter().min().unwrap();

    let mut ans = balls.len();

    'outer: for k in 1..=min_freq {
      let mut total = 0usize;
      for &f in &freqs {
        let q = f / k;
        let r = f % k;
        // feasibility: r groups of size k need to fit alongside groups of size k+1
        // condition: r <= q (i.e., we can reduce a*(k+1) groups to cover remainder)
        if r > q {
          continue 'outer;
        }
        total += (f + k) / (k + 1); // ceil(f / (k+1))
      }
      if total < ans {
        ans = total;
      }
    }

    ans as i32
  }
}