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

Problem 2910

Abstract / Summary

Assign students to groups so that no two with the same favorite subject are together and each group has at most two students, using the fewest groups possible.

Note

The full problem description, including helpful examples, can be found on LeetCode.

<< previous (2909) (2913) next >>

Python 2910.py

class Solution:
    def minGroupsForValidAssignment(self, balls: List[int]) -> int:
        # count balls
        freq = defaultdict(int)
        for b in balls:
            freq[b] += 1

        # drop keys
        values = sorted(freq.values())
        del freq

        # boxes are at most one unit bigger than most rare value
        high = min(values) + 1

        # try large box sizes first
        for capacity in range(high, 0, -1):
            boxes = 0

            for f in values:
                # all boxes are either full (= capacity) or almost full (= capacity - 1)
                full, last = divmod(f, capacity)
                while last > 0:
                    # one more box that is almost full
                    boxes += 1
                    f     -= capacity - 1

                    # impossible
                    if f < 0:
                        boxes = -1
                        break

                    # try again
                    full, last = divmod(f, capacity)

                if boxes < 0:
                    break

                boxes += full

            if boxes > 0:
                return boxes

Difficulty

This problem is ranked as

easy medium hard

and has an acceptance rate of about 25% (60k+ submissions).

Typical patterns to solve this problem:

Array
Greedy
Hash Table

I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided Solution.minGroupsForValidAssignment method determines the smallest number of groups (boxes) needed to distribute a multiset of balls, where each ball is identified by an integer value. The algorithm first aggregates the frequency of each distinct ball value, then explores possible group capacities in descending order, constructing groups that are either completely filled or one unit short of full. The first capacity that yields a feasible grouping returns the total number of groups required.

Frequency Counting

The initial phase builds a histogram of ball occurrences.

freq = defaultdict(int)
for b in balls:
    freq[b] += 1

Using defaultdict(int) eliminates the need for explicit existence checks, allowing a single pass over the input list to produce a mapping from ball value to its count.

Preparing Sorted Frequencies

Only the frequency counts are relevant for the grouping logic. The code extracts these counts, sorts them, and discards the original dictionary to free memory.

values = sorted(freq.values())
del freq

Sorting the frequencies enables deterministic processing of the counts from smallest to largest, which is useful for the subsequent capacity evaluation.

Determining the Upper Bound for Capacity

The algorithm defines an upper limit for the group capacity based on the smallest frequency.

high = min(values) + 1

Since a group can be at most one unit larger than the rarest ball count, this bound guarantees that any feasible capacity will be examined.

Capacity Exploration Loop

The core of the method iterates over possible capacities from the computed upper bound down to one.

for capacity in range(high, 0, -1):
    boxes = 0
    ...

Descending iteration ensures that the first successful capacity corresponds to the minimal number of groups, because larger capacities tend to produce fewer groups.

Processing Each Frequency

Within the capacity loop, each frequency f is examined to determine how many full and almost-full groups it contributes.

full, last = divmod(f, capacity)
while last > 0:
    boxes += 1
    f     -= capacity - 1
    if f < 0:
        boxes = -1
        break
    full, last = divmod(f, capacity)

divmod simultaneously yields the quotient (full) and remainder (last). The while loop handles the remainder by allocating an additional group that is one unit short of the capacity (capacity - 1). If subtracting this amount drives f negative, the current capacity is deemed impossible, signaled by setting boxes to -1 and breaking out.

Accumulating Full Groups

After the remainder handling, the number of completely filled groups contributed by the current frequency is added.

boxes += full

If at any point boxes becomes negative, the outer frequency loop aborts early, moving to the next smaller capacity.

Successful Capacity Detection

When all frequencies have been processed without triggering the impossibility flag, the method returns the total number of groups for the current capacity.

if boxes > 0:
    return boxes

Because capacities are examined from high to low, this return yields the minimal group count that satisfies the constraints.

Edge Cases Handled

The implementation gracefully manages several boundary conditions:

Single-element input: With only one ball, values contains a single count of 1. The high bound becomes 2, and the capacity loop quickly finds a feasible grouping with one box.
Uniform frequencies: When all ball values appear the same number of times, the while loop may never execute because last is zero, leading to a direct accumulation of full groups.
Capacity of one: The loop includes capacity = 1. In this extreme case, every ball requires its own box, and the algorithm correctly computes the total number of balls as the group count.
Large remainder relative to capacity: The inner while loop repeatedly creates almost-full boxes until the remainder is eliminated, ensuring that any combination of full and almost-full boxes can be represented.
Impossible capacity detection: By checking if f < 0 after subtracting capacity - 1, the code identifies capacities that cannot accommodate the current frequency distribution, preventing futile continuation.

Performance Optimizations

Several design choices contribute to efficient execution:

Single pass histogram: Building the frequency map in one traversal avoids multiple scans of the input list.
In-place deletion of the histogram: del freq releases the dictionary after extracting the needed values, reducing memory pressure for large inputs.
Sorted frequencies: Ordering the counts once allows the capacity loop to process them in a predictable sequence, which can improve cache locality.
Early termination on impossibility: Setting boxes to -1 and breaking out of both inner loops as soon as an invalid state is detected prevents unnecessary computation for the current capacity.
Descending capacity order: Starting from the highest plausible capacity reduces the number of iterations needed to locate the minimal group count, because larger capacities tend to satisfy the constraints with fewer groups.
Integer arithmetic with divmod: Using divmod avoids separate division and modulo operations, streamlining the calculation of full groups and remainders.

written by openai gpt

ELI5 - Simplified Explanation

Imagine you have a big pile of colorful balls, and some colors have more balls than others. The goal is to sort these balls into little boxes so that every box holds the same number of balls, or maybe just one less than that number.

First, the code looks at the piles to see how many balls of each color there are. It writes these counts down on a piece of paper. It starts by checking the color that has the fewest balls because that tells it the biggest possible size a box can be.

Then, it tries out different box sizes starting from that biggest size. For each size, it tests if all the balls can fit perfectly into the boxes following the rule that every box must be full or almost full.

If it finds a size that works for every single color, it counts up all the boxes it used. If it cannot make it work, it simply tries a smaller box size instead. It keeps doing this until it finds the right fit for everyone.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

n = 27 | median = 7 | μ = 6.15 | σ = 1.80

Complexity Analysis

not analyzed yet

	author
www	AlgoMonster	C++		Java		Python		TS
WalkCCC	C++		Java		Python
leetcode.ca	C++		Java	Go	Python	Rust	TS
Progiez	C++		Java		Python
github	charles-wangkai			Java
everthis		JS
fsq	C++
wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	C++
wisdompeak	C++

Videos

These are a few popular YouTube videos for this problem:

Abhinav Awasthi 11 mins

Minimum Number of Groups to Create a Valid Assignment Leetcode | Weekly Contest 368 | Solutions

TechTalk 10 mins

2910. Minimum Number of Groups to Create a Valid Assignment - Weekly Contest 368

Ayush Rao 13 mins

2910. Minimum Number of Groups to Create a Valid Assignment || Maths 🔥 || T.C Brute Force 🔥