DSA problem
Magnetic Force Between Two Balls
In the universe Earth C-137, Rick discovered a special form of magnetic force between two balls if they are put in his new invented basket. Rick has n empty baskets, the i-th basket is at position[i]. Morty has m balls and needs to distribute the balls into the baskets such that the minimum magnetic force between any two balls is maximum. The magnetic force between two balls at positions x and y is |x - y|. Return the maximum possible minimum force.
This is binary search the answer on a max-min objective. Define canPlace(d) = "can we place all m balls in distinct baskets such that every consecutive pair is at distance at least d?" The predicate is monotonic in d: if you can guarantee gap d, you can certainly guarantee any smaller gap. So the set of feasible d values is a prefix [0, d*] and binary searching for d* works.
The predicate is greedy: sort positions ascending. Place the first ball at position[0]. Walk forward, placing the next ball at the earliest basket whose distance from the previously placed ball is at least d. Stop when you've placed m balls or run out of baskets. This greedy is optimal because placing earlier (smaller index) leaves the most room for the remaining balls.
The search range is [1, max(position) - min(position)]. d = 1 always works if there are at least m distinct positions (problem guarantees m <= n). d > max - min cannot fit two balls, so it's an upper bound. Use the upper-bound shape: while lo < hi, set mid = lo + (hi - lo + 1) / 2 (the +1 prevents infinite loop), and on canPlace(mid) set lo = mid, else hi = mid - 1. Time O(n log(n + max)).
Examples
position = [1,2,3,4,7], m = 33position = [5,4,3,2,1,1000000000], m = 2999999999position = [1,2,3,4,5,6,7,8,9,10], m = 43Constraints
- n == position.length
- 2 <= n <= 10^5
- 1 <= position[i] <= 10^9
- All integers in position are distinct.
- 2 <= m <= position.length
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.