Problem Description

You have a collection of numbered balls that need to be sorted into boxes following two specific rules:

1. Same box, same value: All balls in the same box must have the same number on them. However, if you have multiple balls with the same number, you can distribute them across different boxes.

2. Balanced distribution: The largest box can contain at most one more ball than the smallest box.

Your task is to find the minimum number of boxes needed to sort all the balls while following these rules.

For example, if you have balls [3,2,3,2,3]:

• You can put the three balls numbered 3 in one box: [3,3,3]
• You can put the two balls numbered 2 in another box: [2,2]
• This gives you 2 boxes total, with sizes 3 and 2 (difference of 1), which satisfies the rules

In another example with balls [10,10,10,3,1,1]:

• You cannot put all three balls numbered 10 in one box because that would create a box of size 3
• To maintain balance with other numbers, you need to split them: [10], [10,10], [3], [1,1]
• This gives you 4 boxes with sizes 1, 2, 1, and 2, maintaining the balance requirement

The algorithm counts the frequency of each number, then tries different group sizes starting from the minimum frequency down to 1. For each potential group size k, it checks if all frequencies can be divided into groups of size k or k+1. The formula (v + k) // (k + 1) calculates the minimum number of groups needed for a frequency v when allowing group sizes of k and k+1.

Intuition

The key insight is that we need to distribute balls with the same number into groups where all groups have similar sizes (differing by at most 1). Let's think about this step by step.

First, we count how many balls we have of each number. For instance, if we have 5 balls numbered 3 and 2 balls numbered 7, we need to figure out how to split these into groups.

The critical observation is that the minimum group size is constrained by the number that appears least frequently. Why? Because if a number appears only twice, we can't make groups of size 3 or larger for that number. This gives us an upper bound on possible group sizes.

Now, if we decide on a target group size k, we can only create groups of size k or k+1 (to satisfy the balance requirement). For each frequency v:

• If v is small compared to k, we might not be able to form even a single group of size k
• The condition v // k < v % k checks if we can't distribute v items into groups of size k and k+1. This happens when the remainder is too large compared to the number of complete groups we can form.

The strategy of trying group sizes from largest to smallest makes sense because:

1. Larger groups mean fewer total boxes (which is what we want to minimize)
2. Once we find a valid group size that works for all frequencies, it's guaranteed to be optimal

The formula (v + k) // (k + 1) cleverly calculates the minimum number of groups needed. It essentially asks: "If I can use groups of size k+1 (the larger size), how many groups do I need?" This greedy approach of using as many large groups as possible minimizes the total number of groups while maintaining the balance constraint.

Learn more about Greedy patterns.

Solution Approach

The implementation follows a systematic approach using a hash table and enumeration strategy.

Step 1: Count Frequencies We start by using a Counter (hash table) to count the occurrences of each number in the array. This gives us cnt where each key is a unique number and its value is the frequency of that number.

Step 2: Determine Search Range We find the minimum frequency among all numbers using min(cnt.values()). This minimum frequency k serves as our starting point because we cannot have groups larger than the smallest frequency (otherwise that number couldn't form even one complete group).

Step 3: Enumerate Group Sizes We enumerate possible group sizes from k down to 1. For each potential group size k, we allow groups of size either k or k+1 to maintain the balance requirement.

Step 4: Validate Group Size For each group size k, we check if all frequencies can be divided into valid groups:

• For each frequency v in cnt.values():
  • We check the condition v // k < v % k
  • This condition fails when we can't distribute v items into groups of size k and k+1
  • If this happens, we have too many leftover items that can't form proper groups
  • When this condition fails for any frequency, we skip this group size and try a smaller one

Step 5: Calculate Minimum Groups If a group size k is valid for all frequencies:

• For each frequency v, we calculate the minimum number of groups using (v + k) // (k + 1)
• This formula greedily creates as many groups of size k+1 as possible
• The logic: if we have v items and want groups of size k+1, we need ⌈v/(k+1)⌉ groups
• The expression (v + k) // (k + 1) is equivalent to the ceiling division

Step 6: Return Result Since we enumerate from larger to smaller group sizes, the first valid configuration we find gives us the minimum number of boxes. We immediately return this answer.

The time complexity is O(n + m × min_freq) where n is the length of the input array and m is the number of unique values, while the space complexity is O(m) for the hash table.

Example Walkthrough

Let's walk through the solution with the array [2,2,2,3,3,1,1,1,1].

Step 1: Count Frequencies First, we count how many times each number appears:

• Number 1 appears 4 times
• Number 2 appears 3 times
• Number 3 appears 2 times

So our frequency map is: {1: 4, 2: 3, 3: 2}

Step 2: Find Minimum Frequency The minimum frequency is 2 (from number 3). This means our maximum possible group size is 2, because we can't make groups larger than 2 for the number that appears only twice.

Step 3: Try Group Size k = 2 Let's check if we can use groups of size 2 or 3 (k and k+1):

For frequency 4 (number 1):

• Check condition: 4 // 2 < 4 % 2 → 2 < 0 → False ✓ (valid)
• Calculate groups needed: (4 + 2) // 3 = 6 // 3 = 2 groups

For frequency 3 (number 2):

• Check condition: 3 // 2 < 3 % 2 → 1 < 1 → False ✓ (valid)
• Calculate groups needed: (3 + 2) // 3 = 5 // 3 = 1 group

For frequency 2 (number 3):

• Check condition: 2 // 2 < 2 % 2 → 1 < 0 → False ✓ (valid)
• Calculate groups needed: (2 + 2) // 3 = 4 // 3 = 1 group

All frequencies pass the validation! Total groups = 2 + 1 + 1 = 4 boxes

Step 4: Verify the Distribution The actual distribution would be:

• Number 1: [1,1] and [1,1] (2 boxes of size 2)
• Number 2: [2,2,2] (1 box of size 3)
• Number 3: [3,3] (1 box of size 2)

Box sizes are: 2, 2, 3, 2. The largest box (3) and smallest box (2) differ by exactly 1, satisfying our balance requirement.

Since k = 2 worked, we don't need to try smaller values. The answer is 4 boxes.

Solution Implementation

Time and Space Complexity

The time complexity is O(n × m), where n is the length of the array nums and m is the minimum frequency value among all elements. The space complexity is O(n).

Time Complexity Analysis:

• Creating the Counter takes O(n) time to iterate through all elements in nums
• Finding min(cnt.values()) takes O(k) time where k is the number of unique elements (at most n)
• The outer loop runs from min(cnt.values()) down to 1, which is at most m iterations where m = min(cnt.values())
• The inner loop iterates through all values in cnt.values(), which has at most n unique elements
• Each inner loop operation (division, modulo, addition) takes O(1) time
• Total: O(n) + O(n × m) = O(n × m)

In the worst case where all elements appear only once, m = 1 and the complexity becomes O(n), matching the reference answer. However, in the general case, the complexity is O(n × m).

Space Complexity Analysis:

• The Counter cnt stores at most n key-value pairs (when all elements are unique), requiring O(n) space
• Other variables (k, ans, v) use O(1) space
• Total: O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Group Size Validation Logic

The condition full_groups < remainder (or v // k < v % k) is often misunderstood. Many developers incorrectly think this checks if we can form groups of exactly size k.

Why this is wrong: The algorithm allows groups of size k OR k+1, not just k. The condition actually checks if we can redistribute the remainder elements among the full groups to form groups of size k+1.

Example of the pitfall:

• If we have 7 balls and k=2: 7 // 2 = 3 full groups, 7 % 2 = 1 remainder
• Since 3 >= 1, we CAN form valid groups: we take one element from each of 1 full group and combine with the remainder to get groups of sizes [2, 2, 3]
• A common mistake is thinking we need exactly groups of size 2, which would fail

Solution: Remember that when full_groups >= remainder, we can "upgrade" remainder number of groups from size k to size k+1 by redistributing elements.

2. Incorrect Group Count Calculation

Using frequency // group_size or frequency // (group_size + 1) directly to count groups is incorrect.

Why this is wrong: These formulas assume all groups are the same size, but we're allowed (and often need) mixed sizes of k and k+1.

Example of the pitfall:

• If we have 5 balls and k=2:
  • Wrong: 5 // 2 = 2 groups (leaves 1 ball ungrouped)
  • Wrong: 5 // 3 = 1 group (leaves 2 balls ungrouped)
  • Correct: (5 + 2) // 3 = 2 groups of sizes [2, 3]

Solution: Use the ceiling division formula (frequency + group_size) // (group_size + 1) which correctly calculates the minimum number of groups when allowing both sizes k and k+1.

3. Starting from 1 Instead of Minimum Frequency

Attempting group sizes starting from 1 and going up, or trying all possible values without optimization.

Why this is wrong:

• Starting from 1 finds larger group counts first (less optimal)
• The maximum valid group size is bounded by the minimum frequency
• If any number appears only twice, you cannot have groups larger than 2

Solution: Always start from min(frequency_map.values()) and iterate downward. This ensures you find the minimum number of groups first and avoid checking impossible group sizes.