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] <= 109Problem Overview: You are given an array of integers and must split elements into groups so that each group contains identical values and the size difference between any two groups is at most 1. The goal is to minimize the total number of groups. Since elements with different values cannot mix, the problem reduces to analyzing the frequency of each value and distributing those counts into valid group sizes.
Approach 1: Greedy Distribution Based on Frequency (O(n + m * k) time, O(m) space)
Start by counting occurrences of each value using a hash map. If a value appears f times, you must split those f elements into groups whose sizes differ by at most 1. The greedy insight is to try the smallest feasible base group size derived from the minimum frequency across all values. For a candidate size k, check whether every frequency f can be expressed using groups of size k or k+1. Iterate possible k values from the minimum frequency downward and compute the required number of groups using integer division. This approach relies heavily on frequency counting via a hash table and a greedy choice that minimizes total groups while keeping group sizes balanced.
Approach 2: Balancing Frequency Distributions (O(n + m * k) time, O(m) space)
This method focuses on balancing the number of groups each frequency contributes. After building a frequency map, you treat each frequency as needing to be decomposed into several nearly equal groups. For a candidate base size x, compute how many groups are required if each group contains either x or x+1 elements. If a frequency cannot be distributed under that constraint, the candidate size is invalid and you try the next smaller size. The balancing step ensures the difference between group sizes never exceeds one. This approach combines ideas from greedy algorithms and counting techniques on arrays to systematically minimize the group count.
Recommended for interviews: The greedy frequency distribution approach is what most interviewers expect. It demonstrates that you can convert the problem into a frequency analysis task and reason about valid group sizes mathematically. A brute-force attempt to simulate group creation shows basic understanding, but the optimized greedy check shows stronger algorithmic insight and clean reasoning about constraints.
This approach focuses on counting the frequency of each unique ball type and distributing them into boxes, prioritizing minimizing deviation in box sizes.
In this solution, we calculate the frequency of each ball using a Counter. The number of boxes is determined by the highest frequency of any single ball number. This ensures that while distributing, the max box count rule is maintained, as any imbalance would require fewer max frequency boxes than needed.
Time Complexity: O(n), where n is the number of balls.
Space Complexity: O(n), storing the frequency count.
This approach works by first computing the frequency of each ball type, then attempts to distribute the balls such that the resulting box configuration is balanced as specified.
The C++ solution uses an unordered_map to track ball frequency and computes the number of required boxes by determining the maximum frequency. This ensures a nearly uniform distribution.
Time Complexity: O(n), where n is the number of balls.
Space Complexity: O(n) for the frequency map.
We use a hash table cnt to count the number of occurrences of each number in the array nums. Let k be the minimum value of the number of occurrences, and then we can enumerate the size of the groups in the range [k,..1]. Since the difference in size between each group is not more than 1, the group size can be either k or k+1.
For the current group size k being enumerated, we traverse each occurrence v in the hash table. If \lfloor \frac{v}{k} \rfloor < v bmod k, it means that we cannot divide the occurrence v into k or k+1 groups with the same value, so we can skip this group size k directly. Otherwise, it means that we can form groups, and we only need to form as many groups of size k+1 as possible to ensure the minimum number of groups. Therefore, we can divide v numbers into \lceil \frac{v}{k+1} \rceil groups and add them to the current enumerated answer. Since we enumerate k from large to small, as long as we find a valid grouping scheme, it must be optimal.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.
| Approach | Complexity |
|---|---|
| Greedy Distribution Based on Frequency | Time Complexity: O(n), where n is the number of balls. |
| Balancing Frequency Distributions | Time Complexity: O(n), where n is the number of balls. |
| Hash Table + Enumeration | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Distribution Based on Frequency | O(n + m * k) | O(m) | General case; efficient when using frequency counting and testing valid group sizes |
| Balancing Frequency Distributions | O(n + m * k) | O(m) | Useful when reasoning about equalized group sizes and validating distributions mathematically |
Minimum Number of Groups to Create a Valid Assignment Leetcode | Weekly Contest 368 | Solutions • Abhinav Awasthi • 2,875 views views
Watch 8 more video solutions →Practice Minimum Number of Groups to Create a Valid Assignment with our built-in code editor and test cases.
Practice on FleetCode