Scale Engineer

Minimum Number of Groups to Create a Valid Assignment

Med
#2591Time: 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).1 company
Patterns
Greedy
Data structures
ArrayHash Table
Companies
BNY Mellon

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

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;    }}

Complexity

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).

Trade-offs

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.

Solutions

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;      }    }  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem