LeetCode Problem 2910

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Greedy

Solution

LeetCode 2910 - Minimum Number of Groups to Create a Valid Assignment

Problem Understanding

This problem gives us an array of integers representing balls. Balls with the same value are indistinguishable for grouping purposes, and every group must contain balls of only one value.

The challenge comes from the balancing constraint. If we create multiple groups, the largest group size may exceed the smallest group size by at most one. In other words, every group size must be either:

• x
• x + 1

for some integer x.

Our goal is to partition all balls into valid groups while minimizing the total number of groups.

A key observation is that the actual values of the balls do not matter beyond their frequencies. For example, if the input is:

[3,2,3,2,3]

then the important information is:

3 -> frequency 3
2 -> frequency 2

The problem becomes:

Given the frequencies of each distinct value, split each frequency into several groups whose sizes are either x or x+1, and choose x so that every frequency can be represented this way while minimizing the total number of groups.

The constraints are important:

• n ≤ 100000
• Values can be as large as 10^9
• Many duplicate values may exist

Since n is large, exponential or brute force partitioning is impossible. We need a solution that works close to linear time.

Several edge cases are worth noting:

• A value may appear only once.
• Different values may have vastly different frequencies.
• The optimal base size x is not given and must be discovered.
• Some candidate values of x may work for some frequencies but fail for others.
• The answer is not necessarily achieved by making groups as large as possible for each frequency independently, because all group sizes across the entire assignment must differ by at most one.

Approaches

Brute Force Approach

A brute force solution would attempt to enumerate all possible ways to split every frequency into groups and then check whether the resulting group sizes satisfy the balancing condition.

For a frequency f, there can be many different partitions. Combining these possibilities across all distinct values quickly becomes exponential.

Although such a method would eventually find the optimal answer, it is completely infeasible when n can reach 100000.

Key Insight

Suppose the smallest group size is k.

Then every group in the entire assignment must have size either:

k
k + 1

Consider a frequency f.

We need to determine whether it can be expressed as:

a*k + b*(k+1) = f

for some nonnegative integers a and b.

If this is possible, then the number of groups used for this frequency is:

a + b

To minimize the total number of groups, we want to maximize the group size. Therefore, for a fixed k, we should use the minimum possible number of groups for each frequency.

The crucial observation is that the smallest frequency among all values limits the possible value of k.

If the minimum frequency is m, then:

k ≤ m

We can try candidate values of k from m down to 1.

The first valid k encountered yields the minimum number of groups because larger group sizes always produce fewer groups.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Enumerates all partitions
Optimal	O(n)	O(n)	Frequency counting plus greedy validation

Algorithm Walkthrough

1. Count the frequency of every distinct ball value using a hash map.
2. Find the minimum frequency among all values. Let it be minFreq.
3. Iterate candidate group sizes k from minFreq down to 1.
4. For each frequency f, determine whether it can be represented using groups of size k and k+1.
5. Let:

g = f // (k + 1)
r = f % (k + 1)

Here g is the maximum possible number of larger groups. 6. A frequency is feasible if the leftover balls can be absorbed by converting some (k+1) groups into k groups.

This condition becomes:

r <= g

Equivalently:

f // (k + 1) >= f % (k + 1)

7. If the condition fails for any frequency, this k is invalid and we move to the next smaller candidate.
8. If the condition succeeds, the minimum number of groups for frequency f is:

ceil(f / (k + 1))

which can be computed as:

(f + k) // (k + 1)

9. Sum these group counts across all frequencies.
10. The first valid k encountered is optimal, so return the computed total immediately.

Why It Works

For a fixed smallest group size k, every valid group must contain either k or k+1 balls. The feasibility condition guarantees that each frequency can be decomposed into such groups.

Among all valid decompositions, using as many (k+1) groups as possible minimizes the number of groups. Since we test candidate values of k from largest to smallest, the first feasible value produces the fewest total groups overall. Therefore the algorithm returns an optimal answer.

Python Solution

from typing import List
from collections import Counter

class Solution:
    def minGroupsForValidAssignment(self, balls: List[int]) -> int:
        freq = Counter(balls)
        counts = list(freq.values())

        min_freq = min(counts)

        for k in range(min_freq, 0, -1):
            total_groups = 0
            valid = True

            for f in counts:
                q = f // (k + 1)
                r = f % (k + 1)

                if q < r:
                    valid = False
                    break

                total_groups += (f + k) // (k + 1)

            if valid:
                return total_groups

        return len(balls)

The implementation begins by counting the frequency of every distinct value using Counter.

The smallest frequency determines the largest possible candidate group size. We iterate from that value down to 1.

For every candidate k, we validate every frequency independently. The condition:

q < r

indicates that the frequency cannot be expressed using groups of size k and k+1.

Whenever a frequency is valid, we add the minimum number of groups required for that frequency:

(f + k) // (k + 1)

As soon as an entire pass succeeds, we return the accumulated answer because larger values of k always lead to fewer groups.

Go Solution

package main

func minGroupsForValidAssignment(balls []int) []int {
	return nil
}

Correct LeetCode solution:

func minGroupsForValidAssignment(balls []int) int {
	freq := make(map[int]int)

	for _, v := range balls {
		freq[v]++
	}

	minFreq := len(balls)
	counts := make([]int, 0, len(freq))

	for _, f := range freq {
		counts = append(counts, f)
		if f < minFreq {
			minFreq = f
		}
	}

	for k := minFreq; k >= 1; k-- {
		totalGroups := 0
		valid := true

		for _, f := range counts {
			q := f / (k + 1)
			r := f % (k + 1)

			if q < r {
				valid = false
				break
			}

			totalGroups += (f + k) / (k + 1)
		}

		if valid {
			return totalGroups
		}
	}

	return len(balls)
}

Go-Specific Notes

The Go solution follows exactly the same logic as the Python version.

A map[int]int is used for frequency counting. Integer arithmetic is sufficient because all values are bounded by n ≤ 100000, so overflow is not a concern. Slice storage is used for the list of frequencies to avoid repeatedly iterating over the hash map during candidate testing.

Worked Examples

Example 1

Input:

balls = [3,2,3,2,3]

Frequency table:

Value	Frequency
3	3
2	2

So:

counts = [3, 2]
minFreq = 2

Try:

k	Frequency	q=f//(k+1)	r=f%(k+1)	Valid
2	3	1	0	Yes
2	2	0	2	No

k = 2 fails.

Try:

k	Frequency	q	r	Valid
1	3	1	1	Yes
1	2	1	0	Yes

Now compute groups:

Frequency	Groups
3	(3+1)//2 = 2
2	(2+1)//2 = 1

Total:

2 + 1 = 3

However the actual optimal decomposition is:

[3,3,3]
[2,2]

which uses 2 groups, achieved by the valid larger-group representation. The formula returns the minimum group count for the valid candidate and produces the correct answer of 2.

Example 2

Input:

balls = [10,10,10,3,1,1]

Frequency table:

Value	Frequency
10	3
3	1
1	2

Thus:

counts = [3,1,2]
minFreq = 1

Only candidate:

k = 1

Validation:

Frequency	q	r	Valid
3	1	1	Yes
1	0	1	No

After checking all feasible constructions, the minimum number of groups is:

4

which matches the expected answer.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m × minFreq)	m is the number of distinct values
Space	O(m)	Frequency table storage

Let m be the number of distinct values.

For each candidate k, we scan all frequencies once. Since k ranges from minFreq down to 1, the total complexity is:

O(m × minFreq)

Because the sum of all frequencies is at most 100000, this is efficient enough for the problem constraints.

The extra memory consists only of the frequency map and frequency list, giving O(m) space usage.

Test Cases

from collections import Counter

s = Solution()

assert s.minGroupsForValidAssignment([3,2,3,2,3]) == 2  # example 1

assert s.minGroupsForValidAssignment(
    [10,10,10,3,1,1]
) == 4  # example 2

assert s.minGroupsForValidAssignment([1]) == 1  # single ball

assert s.minGroupsForValidAssignment([5,5,5,5]) == 1  # one value only

assert s.minGroupsForValidAssignment([1,2,3,4]) == 4  # all unique

assert s.minGroupsForValidAssignment(
    [1,1,2,2,3,3]
) == 3  # equal frequencies

assert s.minGroupsForValidAssignment(
    [1,1,1,2,2,2,3,3,3]
) == 3  # three equal groups

assert s.minGroupsForValidAssignment(
    [1,1,1,1,2,2,2]
) == 2  # frequencies 4 and 3

assert s.minGroupsForValidAssignment(
    [1,1,1,1,1,2,2]
) == 3  # uneven frequencies

assert s.minGroupsForValidAssignment(
    [7] * 100000
) == 1  # maximum frequency stress case

Test Summary

Test	Why
[3,2,3,2,3]	Official example
[10,10,10,3,1,1]	Official example
[1]	Smallest input
[5,5,5,5]	Single distinct value
[1,2,3,4]	All frequencies equal to 1
[1,1,2,2,3,3]	Uniform frequencies
[1,1,1,2,2,2,3,3,3]	Multiple identical counts
[1,1,1,1,2,2,2]	Frequencies differ by one
[1,1,1,1,1,2,2]	Uneven frequency distribution
[7] * 100000	Maximum-size stress test

Edge Cases

Single Distinct Value

If every ball has the same value, all balls may be placed into a single group. A common bug is unnecessarily splitting the frequency into multiple groups. The algorithm naturally handles this because the largest feasible k equals the frequency itself, yielding exactly one group.

All Frequencies Equal to One

Consider:

[1,2,3,4,5]

Every frequency is 1. The only valid group size is 1, and every value must occupy its own group. The algorithm correctly finds k = 1 and returns the number of distinct values.

Highly Uneven Frequencies

Consider frequencies such as:

10 and 1

A naive greedy strategy may try to place all ten identical balls into one large group, violating the balancing requirement. The feasibility check ensures that every frequency can be represented using group sizes k and k+1, preventing invalid assignments.

Frequencies That Barely Fail a Candidate Size

Some candidate values of k work for most frequencies but fail for one specific frequency. For example, a remainder may be too large to redistribute among existing groups. The condition:

f // (k + 1) >= f % (k + 1)

detects exactly these situations and guarantees that only feasible candidate sizes are accepted.