Minimum Number of Groups to Create a Valid Assignment Solution
Minimum Number of Groups to Create a Valid Assignment solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Minimum Number of Groups to Create a Valid Assignment is a medium coding problem on arrays, hash table and greedy, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Greedy
- Asked at: Amazon, Google
- 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
The CodeKairo swag room has a pile of numbered balls; balls[i] is the number printed on the i-th ball. Every ball must go into a box, following two rules:
- All balls inside one box carry the same number (balls with the same number may still be spread over several boxes).
- The fullest box holds at most one ball more than the emptiest box.
Return the fewest boxes needed.
Example 1
Input: balls = [3,2,3,2,3]
Output: 2
Explanation: One box with the three 3s and one box with the two 2s: sizes 3 and 2 differ by one.
Example 2
Input: balls = [10,10,10,3,1,1]
Output: 4
Explanation: The lone 3 forces boxes of size 1 or 2: `[10,10]`, `[10]`, `[3]`, `[1,1]`.
Example 3
Input: balls = [7,7,7,7,7,7,7,1,1,1]
Output: 3
Explanation: Boxes of sizes 3 or 4: the seven 7s fill a box of 4 and a box of 3, the three 1s fill one box of 3.
Constraints
1 <= balls.length <= 10^51 <= balls[i] <= 10^9
Hints for Minimum Number of Groups to Create a Valid Assignment
Hint 1
Only how many times each number occurs matters, not the numbers themselves.
Hint 2
If the smallest box holds
kballs, every box holdskork + 1, andkcan be at most the rarest number's count.Hint 3
For a fixed
k, a countcneedsg = ceil(c / (k + 1))boxes and works only ifg * k <= c. Trykfrom the largest value down; the firstkthat works for every count gives the answer.
How to solve Minimum Number of Groups to Create a Valid Assignment
Fix the size k of the smallest box. Every box then holds k or k + 1 balls, each number's balls can be packed independently, and a larger k never needs more boxes — so the largest feasible k wins.
Approach
- Count the occurrences of each number; let
mbe the smallest count. - For
kfrommdown to 1: for each countc, takeg = ceil(c / (k + 1))boxes — the fewest that can holdcballs atk + 1each. - Those
gboxes can hold anything fromg * ktog * (k + 1)balls, so the count fits exactly wheng * k <= c. If every count fits, return the sum of thegs. k = 1always fits (ceil(c / 2)boxes of one or two balls), so the loop always returns.
Why it works
The smallest box comes from some number, so k never exceeds the rarest count m. For a fixed k, using fewer than ceil(c / (k + 1)) boxes cannot hold c balls, and using that many works whenever the boxes can be filled to at least k each. Since ceil(c / (k + 1)) only shrinks as k grows, the first feasible k from the top gives the fewest boxes in total.
Complexity
- Time —
O(n + m · d) where d is the number of distinct values - Space —
O(d)
Pitfalls
- Box sizes
{k, k + 1}must work for all numbers at once — check every count for the samek. - Using
ceil(c / k)boxes is the wrong count: the larger box sizek + 1gives fewer boxes. - Starting
kabove the rarest count can never succeed.
Reference solution
Python
from typing import List
from collections import Counter
def minGroupsForValidAssignment(balls: List[int]) -> int:
counts = list(Counter(balls).values())
m = min(counts)
for k in range(m, 0, -1):
total = 0
ok = True
for c in counts:
g = (c + k) // (k + 1)
if g * k > c:
ok = False
break
total += g
if ok:
return total
return 0Java
public static int minGroupsForValidAssignment(int[] balls) {
Map<Integer, Integer> freq = new HashMap<>();
for (int v : balls) freq.merge(v, 1, Integer::sum);
int m = Integer.MAX_VALUE;
for (int c : freq.values()) m = Math.min(m, c);
for (int k = m; k >= 1; k--) {
int total = 0;
boolean ok = true;
for (int c : freq.values()) {
int g = (c + k) / (k + 1);
if ((long) g * k > c) { ok = false; break; }
total += g;
}
if (ok) return total;
}
return 0;
}C++
int minGroupsForValidAssignment(vector<int>& balls) {
unordered_map<int, int> freq;
for (int v : balls) freq[v]++;
int m = INT_MAX;
for (auto& p : freq) m = min(m, p.second);
for (int k = m; k >= 1; k--) {
int total = 0;
bool ok = true;
for (auto& p : freq) {
int c = p.second;
int g = (c + k) / (k + 1);
if ((long long) g * k > c) { ok = false; break; }
total += g;
}
if (ok) return total;
}
return 0;
}JavaScript
var minGroupsForValidAssignment = function(balls) {
var freq = new Map();
for (var i = 0; i < balls.length; i++) freq.set(balls[i], (freq.get(balls[i]) || 0) + 1);
var counts = Array.from(freq.values());
var m = balls.length;
for (var j = 0; j < counts.length; j++) if (counts[j] < m) m = counts[j];
for (var k = m; k >= 1; k--) {
var total = 0, ok = true;
for (var t = 0; t < counts.length; t++) {
var c = counts[t];
var g = Math.floor((c + k) / (k + 1));
if (g * k > c) { ok = false; break; }
total += g;
}
if (ok) return total;
}
return 0;
};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