2910. Minimum Number of Groups to Create a Valid Assignment LeetCode Solution

In this guide, you will get 2910. Minimum Number of Groups to Create a Valid Assignment LeetCode Solution with the best time and space complexity. The solution to Minimum Number of Groups to Create a Valid Assignment problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Minimum Number of Groups to Create a Valid Assignment solution in C++
Minimum Number of Groups to Create a Valid Assignment solution in Java
Minimum Number of Groups to Create a Valid Assignment solution in Python
Additional Resources

2910. Minimum Number of Groups to Create a Valid Assignment LeetCode Solution image

Problem Statement of Minimum Number of Groups to Create a Valid Assignment

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

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

2910. Minimum Number of Groups to Create a Valid Assignment LeetCode Solution in C++

class Solution {
 public:
  int minGroupsForValidAssignment(vector<int>& nums) {
    unordered_map<int, int> count;
    int minFreq = nums.size();

    for (const int num : nums)
      ++count[num];

    for (const auto& [_, freq] : count)
      minFreq = min(minFreq, freq);

    for (int groupSize = minFreq; groupSize >= 1; --groupSize) {
      const int numGroups = getNumGroups(count, groupSize);
      if (numGroups > 0)
        return numGroups;
    }

    throw;
  }

 private:
  // Returns the number of groups if each group's size is `groupSize` or
  // `groupSize + 1`.
  int getNumGroups(unordered_map<int, int>& count, int groupSize) {
    int numGroups = 0;
    for (const auto& [_, freq] : count) {
      const int a = freq / (groupSize + 1);
      const int b = freq % (groupSize + 1);
      if (b == 0) {
        numGroups += a;
      } else if (groupSize - b <= a) {
        // Assign 1 number from `groupSize - b` out of `a` groups to this group,
        // so we'll have `a - (groupSize - b)` groups of size `groupSize + 1`
        // and `groupSize - b + 1` groups of size `groupSize`. In total, we have
        // `a + 1` groups.
        numGroups += a + 1;
      } else {
        return 0;
      }
    }
    return numGroups;
  }
};
/* code provided by PROGIEZ */

2910. Minimum Number of Groups to Create a Valid Assignment LeetCode Solution in Java

class Solution {
  public int minGroupsForValidAssignment(int[] nums) {
    Map<Integer, Integer> count = new HashMap<>();
    int minFreq = nums.length;

    for (final int num : nums)
      count.merge(num, 1, Integer::sum);

    for (final int freq : count.values())
      minFreq = Math.min(minFreq, freq);

    for (int groupSize = minFreq; groupSize >= 1; --groupSize) {
      final int numGroups = getNumGroups(count, groupSize);
      if (numGroups > 0)
        return numGroups;
    }

    throw new IllegalArgumentException();
  }

  // Returns the number of groups if each group's size is `groupSize` or
  // `groupSize + 1`.
  private int getNumGroups(Map<Integer, Integer> count, int groupSize) {
    int numGroups = 0;
    for (final int freq : count.values()) {
      final int a = freq / (groupSize + 1);
      final int b = freq % (groupSize + 1);
      if (b == 0) {
        numGroups += a;
      } else if (groupSize - b <= a) {
        // Assign 1 number from `groupSize - b` out of `a` groups to this group,
        // so we'll have `a - (groupSize - b)` groups of size `groupSize + 1`
        // and `groupSize - b + 1` groups of size `groupSize`. In total, we have
        // `a + 1` groups.
        numGroups += a + 1;
      } else {
        return 0;
      }
    }
    return numGroups;
  }
}
// code provided by PROGIEZ

2910. Minimum Number of Groups to Create a Valid Assignment LeetCode Solution in Python

class Solution:
  def minGroupsForValidAssignment(self, nums: list[int]) -> int:
    count = collections.Counter(nums)
    minFreq = min(count.values())

    for groupSize in range(minFreq, 0, -1):
      numGroups = self.getNumGroups(count, groupSize)
      if numGroups > 0:
        return numGroups

    raise ValueError("Invalid argument")

  def getNumGroups(self, count: dict[int, int], groupSize: int) -> int:
    """Returns the number of groups if each group's size is `groupSize` or `groupSize + 1`."""
    numGroups = 0
    for freq in count.values():
      a = freq // (groupSize + 1)
      b = freq % (groupSize + 1)
      if b == 0:
        # Assign 1 number from `groupSize - b` out of `a` groups to this group,
        # so we'll have `a - (groupSize - b)` groups of size `groupSize + 1`
        # and `groupSize - b + 1` groups of size `groupSize`. In total, we have
        # `a + 1` groups.
        numGroups += a
      elif groupSize - b <= a:
        numGroups += a + 1
      else:
        return 0
    return numGroups
 # code by PROGIEZ