Show problems as
Classic problem #2910MediumArrayHash TableGreedy

Minimum Number of Groups to Create a Valid Assignment

Real-world version: Fewest Crates to Sort the Bearings
Tracked in this browser only
Read Minimum Number of Groups to Create a Valid Assignment on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A tray of bearings is given as balls, where balls[i] is the grade of bearing i.

Every bearing must go into a crate, and a crate may only hold bearings of a single grade. The packing is tidy when any two crates differ in count by at most one.

Return the fewest crates a tidy packing can use.

Examples

Example 1

Input
balls = [5, 5, 5, 5, 5, 6]
Output
4

Grade 6 appears once, so every crate must hold one or two bearings. The five grade 5 bearings need three crates at that size, and the grade 6 bearing needs one of its own.

Example 2

Input
balls = [1, 1, 1, 2]
Output
3

Grade 2 appears once, so every crate must hold one or two bearings. Three crates of one grade-1 bearing each, plus one for the grade 2, gives four.

Example 3

Input
balls = [7, 7, 7]
Output
1

All three bearings share a grade, so a single crate holds them and no other crate exists to differ from.

Constraints

  • 1 <= balls.length <= 10^5
  • 1 <= balls[i] <= 10^9

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def fewest_crates(balls: list[int]) -> int:
Java
public int fewestCrates(int[] balls)

More on the same topics