Magnetic Force Between Two Balls
Medium · Binary Search · Array · Binary Search · Sorting
Problem
There are n empty baskets at distinct positions position[i] along a line; the array is not necessarily sorted. You must place m balls into the baskets, at most one ball per basket. The magnetic force between two balls at positions x and y is |x - y|.
Place the balls so that the smallest force between any two of them is as large as possible, and return that largest possible smallest force.
Examples
Input: position = [1,3,6,10,11], m = 3 Output: 5
Baskets 1, 6 and 11 give gaps of 5 and 5; no placement keeps every gap above 5.
Input: position = [9,2,5], m = 2 Output: 7
Use the two farthest baskets, 2 and 9, for a force of 7.
Input: position = [5,4,3,2,1,1000000000], m = 2 Output: 999999999
Two balls go to the ends: 1 and 1000000000.
Constraints
- n == len(position)
- 2 <= n <= 10^5
- 1 <= position[i] <= 10^9
- All values in position are distinct.
- 2 <= m <= n
Approaches
- Baseline: test every pairwise gap — time O(n³), space O(n²)
Follow-up
The same "maximize the minimum gap" search answers placing cell towers, seating people apart or choosing well-spread sample points. Its mirror, "minimize the maximum load", is the store use case below; both need only a monotone yes/no check.
Related problems
Start free on Cariara · Coding problems · System design studio
