488. Magnetic Force Between Two Balls

Given basket positions along a line and m balls, distribute the balls into baskets so that the minimum magnetic force (the minimum distance between any two balls) is maximized. Return that maximum possible minimum force. Input: '[positions], m'.

Input: '[positions], m'.

Output: Integer — the maximized minimum force.

Examples

Input: [1,2,3,4,7], 3
Output: 3
Explanation: Place at 1,4,7: min distance 3.

Input: [1,5], 2
Output: 4
Explanation: Two baskets, distance 4.

Input: [10,1,2,7,5], 4
Output: 2
Explanation: Best minimum distance is 2.

Constraints

• 2<=m<=n<=10^5
• 1<=position<=10^9

Asked by