All problems

Magnetic Force Between Two Balls

Medium · binary search

A row of empty baskets lies along a straight rail. positions gives the position of each basket on the rail, in strictly increasing order.

You have m magnetic balls and must put each one in a different basket. The balls repel each other, so what matters is the closest pair: the smaller the distance between the two nearest balls, the stronger the push.

Choose the baskets so that the smallest distance between any two balls is as large as possible, and return that distance.

Examples

Example 1

Input: positions = [1, 3, 4, 8, 10], m = 3

Output: 3

Use the baskets at 1, 4 and 8: the distances are 3 and 4, so the closest pair is 3 apart. No choice of three baskets keeps every pair at least 4 apart.

Example 2

Input: positions = [1, 3, 4, 8, 10], m = 2

Output: 9

Put one ball in the first basket and one in the last.

Example 3

Input: positions = [2, 3, 5, 6], m = 4

Output: 1

Every basket is used, so the closest pair is the closest pair of baskets.

Constraints

• 2 <= m <= len(positions) <= 10^5
• 1 <= positions[i] <= 10^6
• positions is strictly increasing.