# Minimum Number of Groups to Create a Valid Assignment
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-number-of-groups-to-create-a-valid-assignment)
Canonical: https://scaleengineer.com/dsa/problems/minimum-number-of-groups-to-create-a-valid-assignment
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array, Hash Table
**Companies:** [BNY Mellon](https://scaleengineer.com/companies/bny-mellon)
---
## 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.

**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 <= 105`
* `1 <= nums[i] <= 109`

# Approaches
## Brute Force Iteration over Group Sizes
This approach involves determining all possible valid sizes for the smallest box, let's call it `k`. A size `k` is valid if every group of same-valued balls can be partitioned into boxes of size `k` or `k+1`. We can iterate through all possible values of `k` and for each `k`, check if it's a valid configuration. If it is, we calculate the total number of boxes required and keep track of the minimum. The range of `k` is taken from 1 up to the maximum count of any ball number, as a box can't be larger than the number of balls available for that value.
**Time:** O(N + M * max_c), where N is the number of balls, M is the number of unique ball values, and `max_c` is the maximum frequency. In the worst case, `max_c` can be O(N), leading to a complexity of O(N*M), which is too slow for the given constraints. · **Space:** O(M), where M is the number of unique ball values. This is for storing the frequencies in a hash map. In the worst case, M can be equal to N, making it O(N).
**Pros:** Conceptually simple and directly follows from the problem definition.
**Cons:** Inefficient due to a large search space for `k`, which can lead to a Time Limit Exceeded (TLE) error on larger inputs.
### Explanation
First, we count the frequency of each ball number. This gives us a set of counts `{c1, c2, ..., cm}`. The size of the smallest box, `k`, can theoretically range from 1 up to the maximum count found, `max_c`.

We iterate `k` from 1 to `max_c`. For each `k`:
- We check if this `k` can lead to a valid assignment. This means for every count `ci`, it must be possible to express `ci` as a sum of numbers, where each number is either `k` or `k+1`.
- A count `c` can be partitioned into groups of size `k` and `k+1` if and only if there exists an integer `T` (number of groups for `c`) such that `c/(k+1) <= T <= c/k`. This is equivalent to checking if `ceil(c/(k+1)) <= floor(c/k)`.
- If this condition holds for all counts `ci`, then `k` is a valid choice. We calculate the total number of boxes for this `k` as the sum of `ceil(ci/(k+1))` for all `ci`.
- We keep track of the minimum total boxes found across all valid `k`.

After checking all possible `k`, we return the minimum number of boxes found.

```java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public int minGroupsForValidAssignment(int[] balls) {
        Map<Integer, Integer> countsMap = new HashMap<>();
        for (int ball : balls) {
            countsMap.put(ball, countsMap.getOrDefault(ball, 0) + 1);
        }

        List<Integer> counts = new ArrayList<>(countsMap.values());
        int max_c = 0;
        for (int count : counts) {
            if (count > max_c) {
                max_c = count;
            }
        }

        int minBoxes = Integer.MAX_VALUE;

        for (int k = 1; k <= max_c; k++) {
            int currentBoxes = 0;
            boolean possible = true;
            for (int c : counts) {
                // Check if count c can be partitioned into groups of size k and k+1
                // This is possible if ceil(c / (k+1)) <= floor(c / k)
                int lower_bound_T = (c + k) / (k + 1); // ceil using integer division
                int upper_bound_T = c / k; // floor using integer division
                
                if (lower_bound_T > upper_bound_T) {
                    possible = false;
                    break;
                }
                currentBoxes += lower_bound_T;
            }

            if (possible) {
                minBoxes = Math.min(minBoxes, currentBoxes);
            }
        }

        return minBoxes;
    }
}
```
### Algorithm
- Use a `HashMap` to count the frequencies of each number in `balls`. Store these counts.
- Find the maximum count, `max_c`, among all frequencies.
- Initialize `min_total_boxes` to a very large value.
- Loop `k` from 1 to `max_c`.
- Inside the loop, assume `k` is valid and initialize `current_total_boxes = 0`.
- For each count `c` in our frequency list:
    - Check if `c` can be partitioned into groups of size `k` and `k+1`. The condition for this is `ceil(c / (k + 1)) <= floor(c / k)`.
    - If it cannot be partitioned, this `k` is invalid. Break the inner loop and proceed to the next `k`.
    - If it can be partitioned, add `ceil(c / (k + 1))` to `current_total_boxes`.
- If the inner loop completed without breaking (meaning `k` is valid for all counts), update `min_total_boxes = min(min_total_boxes, current_total_boxes)`.
- After the outer loop finishes, return `min_total_boxes`.

## Optimized Iteration over Group Sizes
This approach improves upon the brute-force method by observing a key property of the valid group sizes. The size of the smallest box, `k`, cannot be larger than the count of the least frequent ball number. This is because `k` must be a valid size for partitioning every group, including the smallest one. This observation significantly reduces the search space for `k`, leading to a much more efficient solution.
**Time:** O(N + M * min_c), where N is the number of balls, M is the number of unique values, and `min_c` is the minimum frequency. Since `M * min_c <= sum of all counts = N`, the complexity of the loops is bounded by O(N). Thus, the total time complexity is O(N). · **Space:** O(M), where M is the number of unique ball values. This is for storing the frequencies. In the worst case, M can be equal to N, making it O(N).
**Pros:** Highly efficient with a linear time complexity.; Correctly identifies the tightest possible search space for the optimal group size, making it feasible for large inputs.
**Cons:** The logic for why the search space can be reduced requires a slightly deeper analysis of the problem constraints.
### Explanation
The logic is similar to the brute-force approach, but with a crucial optimization. First, we count the frequencies of each ball number, `{c1, c2, ..., cm}`. Let `min_c` be the minimum count among all frequencies.

Any valid smallest box size `k` must be able to partition every count `ci`, including `min_c`. For `k` to be a valid size for partitioning `min_c`, we must have `k <= min_c`. If `k > min_c`, then `floor(min_c / k)` would be 0. However, `ceil(min_c / (k+1))` is at least 1 (since `min_c >= 1`). The condition `ceil <= floor` becomes `1 <= 0`, which is false. Therefore, any `k > min_c` is invalid.

This means we only need to search for the optimal `k` in the range `[1, min_c]`. The rest of the algorithm is the same: iterate `k` from 1 to `min_c`, check for validity across all counts, calculate the total boxes if valid, and find the minimum.

```java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public int minGroupsForValidAssignment(int[] balls) {
        Map<Integer, Integer> countsMap = new HashMap<>();
        for (int ball : balls) {
            countsMap.put(ball, countsMap.getOrDefault(ball, 0) + 1);
        }

        if (countsMap.isEmpty()) {
            return 0;
        }

        List<Integer> counts = new ArrayList<>(countsMap.values());
        int min_c = Integer.MAX_VALUE;
        for (int count : counts) {
            if (count < min_c) {
                min_c = count;
            }
        }

        int minBoxes = Integer.MAX_VALUE;

        for (int k = 1; k <= min_c; k++) {
            int currentBoxes = 0;
            boolean possible = true;
            for (int c : counts) {
                // Check if count c can be partitioned into groups of size k and k+1
                // This is possible if ceil(c / (k+1)) <= floor(c / k)
                int lower_bound_T = (c + k) / (k + 1); // ceil using integer division
                int upper_bound_T = c / k; // floor using integer division
                
                if (lower_bound_T > upper_bound_T) {
                    possible = false;
                    break;
                }
                currentBoxes += lower_bound_T;
            }

            if (possible) {
                minBoxes = Math.min(minBoxes, currentBoxes);
            }
        }

        return minBoxes;
    }
}
```
### Algorithm
- Use a `HashMap` to count frequencies of each number in `balls`. Store these counts.
- Find the minimum count, `min_c`, among all frequencies.
- Initialize `min_total_boxes` to a very large value.
- Loop `k` from 1 to `min_c`.
- Inside the loop, assume `k` is valid and initialize `current_total_boxes = 0`.
- For each count `c` in our frequency list:
    - Check if `c` can be partitioned into groups of size `k` and `k+1`. The condition is `ceil(c / (k + 1)) <= floor(c / k)`.
    - If it cannot be partitioned, this `k` is invalid. Break the inner loop and continue to the next `k`.
    - If it can be partitioned, add `ceil(c / (k + 1))` to `current_total_boxes`.
- If the inner loop completed (i.e., `k` is valid for all counts), update `min_total_boxes = min(min_total_boxes, current_total_boxes)`.
- Return `min_total_boxes`.

# Solutions
### Java

```java
class Solution {
public
  int minGroupsForValidAssignment(int[] nums) {
    Map<Integer, Integer> cnt = new HashMap<>();
    for (int x : nums) {
      cnt.merge(x, 1, Integer : : sum);
    }
    int k = nums.length;
    for (int v : cnt.values()) {
      k = Math.min(k, v);
    }
    for (;; --k) {
      int ans = 0;
      for (int v : cnt.values()) {
        if (v / k < v % k) {
          ans = 0;
          break;
        }
        ans += (v + k) / (k + 1);
      }
      if (ans > 0) {
        return ans;
      }
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minGroupsForValidAssignment(vector<int> &nums) {
    unordered_map<int, int> cnt;
    for (int x : nums) {
      cnt[x]++;
    }
    int k = 1e9;
    for (auto &[_, v] : cnt) {
      ans = min(ans, v);
    }
    for (;; --k) {
      int ans = 0;
      for (auto &[_, v] : cnt) {
        if (v / k < v % k) {
          ans = 0;
          break;
        }
        ans += (v + k) / (k + 1);
      }
      if (ans) {
        return ans;
      }
    }
  }
};

```

### Python

```python
class Solution:
    def minGroupsForValidAssignment(self, nums: List[int]) -> int: cnt = Counter(nums) for k in range(min(cnt . values()), 0, - 1): ans = 0 for v in cnt . values(): if v // k < v % k: ans = 0 break ans += (v + k) // (k + 1) if ans: return ans

```