problemmediumalgorithmsleetcode-2910leetcode 2910leetcode2910

Minimum Number of Groups to Create a Valid Assignment

MediumUpdated: Aug 2, 2025
Practice on:
LeetCode

Problem

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.

Examples

Example 1


Input: balls = [3,2,3,2,3]

Output: 2

Explanation:

We can sort `balls` into boxes as follows:

  * `[3,3,3]`
  * `[2,2]`

The size difference between the two boxes doesn't exceed one.

Example 2


Input: balls = [10,10,10,3,1,1]

Output: 4

Explanation:

We can sort `balls` into boxes as follows:

  * `[10]`
  * `[10,10]`
  * `[3]`
  * `[1,1]`

You can't use fewer than four boxes while still following the rules. For
example, putting all three balls numbered 10 in one box would break the rule
about the maximum size difference between boxes.

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9

Solution

Method 1 – Greedy Frequency Grouping

Intuition

For each value, split its balls into groups of size ⌈count/boxes⌉, so that the largest and smallest box differ by at most one. The minimum number of boxes is the maximum frequency among all values.

Approach

  1. Count the frequency of each value.
  2. The answer is the maximum frequency among all values.

Code

C++
#include <vector>
#include <unordered_map>
using namespace std;
class Solution {
public:
    int minGroups(vector<int>& balls) {
        unordered_map<int, int> freq;
        for (int x : balls) freq[x]++;
        int ans = 0;
        for (auto& [_, f] : freq) ans = max(ans, f);
        return ans;
    }
};
Go
func minGroups(balls []int) int {
    freq := map[int]int{}
    for _, x := range balls { freq[x]++ }
    ans := 0
    for _, f := range freq {
        if f > ans { ans = f }
    }
    return ans
}
Java
import java.util.*;
class Solution {
    public int minGroups(int[] balls) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int x : balls) freq.put(x, freq.getOrDefault(x, 0) + 1);
        int ans = 0;
        for (int f : freq.values()) ans = Math.max(ans, f);
        return ans;
    }
}
Kotlin
class Solution {
    fun minGroups(balls: IntArray): Int {
        val freq = mutableMapOf<Int, Int>()
        for (x in balls) freq[x] = freq.getOrDefault(x, 0) + 1
        return freq.values.maxOrNull() ?: 0
    }
}
Python
from collections import Counter
class Solution:
    def minGroups(self, balls: list[int]) -> int:
        freq = Counter(balls)
        return max(freq.values())
Rust
use std::collections::HashMap;
impl Solution {
    pub fn min_groups(balls: Vec<i32>) -> i32 {
        let mut freq = HashMap::new();
        for x in balls { *freq.entry(x).or_insert(0) += 1; }
        *freq.values().max().unwrap()
    }
}
TypeScript
class Solution {
    minGroups(balls: number[]): number {
        const freq = new Map<number, number>();
        for (const x of balls) freq.set(x, (freq.get(x) ?? 0) + 1);
        return Math.max(...freq.values());
    }
}

Complexity

  • ⏰ Time complexity: O(n) — n = length of balls.
  • 🧺 Space complexity: O(n) — for frequency map.

Comments