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:
Return the fewest number of boxes to sort these balls following these rules.
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 <= 1051 <= nums[i] <= 109To solve #2910 Minimum Number of Groups to Create a Valid Assignment, first count the frequency of each number using a hash map. Since elements with the same value must be grouped together, the challenge becomes splitting each frequency into valid group sizes while minimizing the total number of groups.
A key observation is that each value can be divided into groups whose sizes differ by at most one (for example k or k+1). We try feasible base group sizes derived from the smallest frequency and check whether every frequency can be partitioned into groups of size k or k+1. For a candidate size, compute the minimum number of groups needed for each frequency and verify the distribution is valid. If it is, accumulate the group counts.
This approach combines greedy reasoning with frequency counting. The hash table stores counts while the greedy check determines the minimal grouping strategy. Overall complexity is typically O(n) for counting plus a small iteration over possible group sizes, with O(n) space for the frequency map.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Map + Greedy Group Size Validation | O(n) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Calculate the frequency of each number.
For each <code>x</code> in the range <code>[1, minimum_frequency]</code>, try to create groups with either <code>x</code> or <code>x + 1</code> indices assigned to them while minimizing the total number of groups.
For each distinct number, using its frequency, check that all its occurrences can be assigned to groups of size <code>x</code> or <code>x + 1</code> while minimizing the number of groups used.
To get the minimum number of groups needed for a number having frequency <code>f</code> to be assigned to groups of size <code>x</code> or <code>x + 1</code>, let <code>a = f / (x + 1)</code> and <code>b = f % (x + 1)</code>. <ul> <li>If <code>b == 0</code>, then we can simply create <code>a</code> groups of size <code>x + 1</code>.</li> <li>If <code>x - b <= a</code>, we can have <code>a - (x - b)</code> groups of size <code>x + 1</code> and <code>x - b + 1</code> groups of size <code>x</code>. So, in total, we have <code>a + 1</code> groups.</li> <li>Otherwise, it's impossible.</li> </ul>
The minimum number of groups needed for some <code>x</code> is the total minimized number of groups needed for each distinct number.
The answer is the minimum number of groups needed for each <code>x</code> in the range <code>[1, minimum_frequency]</code>.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Problems like this are common in FAANG-style interviews because they test frequency counting, greedy reasoning, and edge-case handling. While the exact problem may not appear, similar variations involving grouping and frequency constraints are frequently asked.
A hash table (or dictionary) is the most useful data structure because it efficiently stores the frequency of each value in the array. Once frequencies are known, greedy calculations can determine how many valid groups can be formed from each count.
The optimal approach counts the frequency of each number using a hash map and then greedily tests feasible group sizes. Each frequency is split into groups whose sizes differ by at most one, ensuring the minimum number of groups. This avoids brute force grouping and keeps the solution efficient.
A greedy strategy works because the goal is to minimize the number of groups while keeping their sizes balanced. By choosing the largest feasible group sizes and verifying validity, we can systematically reduce the number of groups without violating the constraints.