Show problems as
Classic problem #2616MediumArrayBinary SearchDynamic ProgrammingGreedySorting

Minimize the Maximum Difference of Pairs

Real-world version: Pairing Gears by Closest Tooth Count
Tracked in this browser only
Read Minimize the Maximum Difference of Pairs on LeetCode(opens in a new tab)

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

A workshop's gears have the tooth counts teeth. A mesh joins two of the gears, and no gear may take part in more than one mesh. The slip of a mesh is how far apart its two tooth counts are.

Form exactly p meshes so that the largest slip among them is as small as it can be, and return that largest slip. When p is zero there is nothing to form and the answer is 0.

Examples

Example 1

Input
teeth = [8, 1, 2, 7, 5, 4], p = 2
Output
1

Sorted, the counts read 1, 2, 4, 5, 7, 8. Meshing 1 with 2 and 4 with 5 gives two meshes that each slip by one, and no pair of meshes gets both slips down to nothing.

Example 2

Input
teeth = [0, 1, 2, 10, 11, 12], p = 3
Output
8

Six gears and three meshes leaves nothing out, so one mesh has to bridge the low group and the high group. Meshing 0 with 1 and 11 with 12 leaves 2 with 10 as the narrowest bridge available.

Example 3

Input
teeth = [5, 8], p = 0
Output
0

No meshes are asked for, so there is no slip to report.

Constraints

  • 1 <= teeth.length <= 10^5
  • 0 <= teeth[i] <= 10^9
  • 0 <= p <= teeth.length / 2

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 minimize_max(teeth: list[int], p: int) -> int:
Java
public int minimizeMax(int[] teeth, int p)

More on the same topics