Skip to main content
Talentd

Minimum Number of Groups to Create a Valid Assignment - Solution & Explanation

MediumArrayHash TableGreedy14 min readAsked at: Amazon
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You are given an array of integers and must split elements into groups so that each group contains identical values and the size difference between any two groups is at most 1. The goal is to minimize the total number of groups. Since elements with different values cannot mix, the problem reduces to analyzing the frequency of each value and distributing those counts into valid group sizes.

Approach 1: Greedy Distribution Based on Frequency (O(n + m * k) time, O(m) space)

Start by counting occurrences of each value using a hash map. If a value appears f times, you must split those f elements into groups whose sizes differ by at most 1. The greedy insight is to try the smallest feasible base group size derived from the minimum frequency across all values. For a candidate size k, check whether every frequency f can be expressed using groups of size k or k+1. Iterate possible k values from the minimum frequency downward and compute the required number of groups using integer division. This approach relies heavily on frequency counting via a hash table and a greedy choice that minimizes total groups while keeping group sizes balanced.

Approach 2: Balancing Frequency Distributions (O(n + m * k) time, O(m) space)

This method focuses on balancing the number of groups each frequency contributes. After building a frequency map, you treat each frequency as needing to be decomposed into several nearly equal groups. For a candidate base size x, compute how many groups are required if each group contains either x or x+1 elements. If a frequency cannot be distributed under that constraint, the candidate size is invalid and you try the next smaller size. The balancing step ensures the difference between group sizes never exceeds one. This approach combines ideas from greedy algorithms and counting techniques on arrays to systematically minimize the group count.

Recommended for interviews: The greedy frequency distribution approach is what most interviewers expect. It demonstrates that you can convert the problem into a frequency analysis task and reason about valid group sizes mathematically. A brute-force attempt to simulate group creation shows basic understanding, but the optimized greedy check shows stronger algorithmic insight and clean reasoning about constraints.

Approach 1: Greedy Distribution Based on Frequency

This approach focuses on counting the frequency of each unique ball type and distributing them into boxes, prioritizing minimizing deviation in box sizes.

In this solution, we calculate the frequency of each ball using a Counter. The number of boxes is determined by the highest frequency of any single ball number. This ensures that while distributing, the max box count rule is maintained, as any imbalance would require fewer max frequency boxes than needed.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(n), where n is the number of balls.
Space Complexity: O(n), storing the frequency count.

Try this approach in the editor →

Approach 2: Balancing Frequency Distributions

This approach works by first computing the frequency of each ball type, then attempts to distribute the balls such that the resulting box configuration is balanced as specified.

The C++ solution uses an unordered_map to track ball frequency and computes the number of required boxes by determining the maximum frequency. This ensures a nearly uniform distribution.

Code

C++C#

C++

C#

Complexity

Time Complexity: O(n), where n is the number of balls.
Space Complexity: O(n) for the frequency map.

Try this approach in the editor →

Approach 3: Hash Table + Enumeration

We use a hash table cnt to count the number of occurrences of each number in the array nums. Let k be the minimum value of the number of occurrences, and then we can enumerate the size of the groups in the range [k,..1]. Since the difference in size between each group is not more than 1, the group size can be either k or k+1.

For the current group size k being enumerated, we traverse each occurrence v in the hash table. If \lfloor \frac{v}{k} \rfloor < v bmod k, it means that we cannot divide the occurrence v into k or k+1 groups with the same value, so we can skip this group size k directly. Otherwise, it means that we can form groups, and we only need to form as many groups of size k+1 as possible to ensure the minimum number of groups. Therefore, we can divide v numbers into \lceil \frac{v}{k+1} \rceil groups and add them to the current enumerated answer. Since we enumerate k from large to small, as long as we find a valid grouping scheme, it must be optimal.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Distribution Based on Frequency

Time Complexity: O(n), where n is the number of balls.
Space Complexity: O(n), storing the frequency count.

Balancing Frequency Distributions

Time Complexity: O(n), where n is the number of balls.
Space Complexity: O(n) for the frequency map.

Hash Table + Enumeration—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy Distribution Based on FrequencyO(n + m * k)O(m)General case; efficient when using frequency counting and testing valid group sizes
Balancing Frequency DistributionsO(n + m * k)O(m)Useful when reasoning about equalized group sizes and validating distributions mathematically

Video Solution

Minimum Number of Groups to Create a Valid Assignment Leetcode | Weekly Contest 368 | Solutions • Abhinav Awasthi • 2,923 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Minimum Number of Groups to Create a Valid Assignment easy or hard?
The problem is rated Medium on LeetCode with an acceptance rate around 25%. The challenge comes from recognizing that the array itself is not important after counting frequencies. The real task is validating whether frequencies can be partitioned into nearly equal group sizes using a greedy check.
Minimum Number of Groups to Create a Valid Assignment Python/Java solution
Python and Java implementations typically start with a dictionary or HashMap to count frequencies. Then they iterate possible base group sizes and compute the number of groups needed using integer division and remainder checks. The logic is identical across languages, with differences only in syntax.
How to solve Minimum Number of Groups to Create a Valid Assignment in O(n)?
First build a frequency map of all values in the array. Determine the minimum frequency and iterate possible base group sizes from that value downward. For each candidate size k, verify that every frequency f can be split into groups of size k or k+1 using division checks. Once a valid configuration is found, sum the number of groups for all frequencies.
What is the best approach for Minimum Number of Groups to Create a Valid Assignment?
The greedy frequency distribution approach is typically the best solution. Count occurrences of each number with a hash map, then test feasible base group sizes derived from the minimum frequency. For each candidate size k, check whether every frequency can be split into groups of size k or k+1. This minimizes the total number of groups while keeping group sizes balanced.
Is Minimum Number of Groups to Create a Valid Assignment asked at Google/Amazon/Meta?
Problems involving frequency grouping and greedy distribution frequently appear in interviews at companies like Google, Amazon, and Meta. This specific LeetCode problem tests reasoning about constraints, counting with hash maps, and greedy validation, which are common interview patterns.
What data structure is used in Minimum Number of Groups to Create a Valid Assignment?
The core data structure is a hash map that stores the frequency of each value in the array. After counting, the algorithm iterates over these frequencies and applies greedy arithmetic checks to determine how many groups are needed for each value.
What is the time complexity of Minimum Number of Groups to Create a Valid Assignment?
The overall time complexity is roughly O(n + m * k), where n is the array length, m is the number of distinct values, and k is the number of candidate group sizes tested. Frequency counting takes O(n), and validation across frequencies is usually small in practice, making the solution close to linear time.

Ready to solve this problem?

Practice Minimum Number of Groups to Create a Valid Assignment with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays