Magnetic Force Between Two Balls
Medium Binary search on the answer (aggressive cows)
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Place m balls into baskets at given positions so that the minimum distance between any two balls is as large as possible. Return that distance.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: place m balls to make the closest pair as far apart as possible ("aggressive cows").
Why this works: if a minimum gap d is possible, every smaller gap is too. Binary search d and place balls greedily from the left.
Example: positions [1, 2, 3, 4, 7], m = 3
d=3: place at 1, 4, 7 ✓d=4: place at 1, 7 only ✗ → answer 3
✦Hints open one at a time
↗Approach
This is the classic "aggressive cows". Binary search d in [1, max − min]. Feasible if the greedy placement fits at least m balls.
</>Solution (Java)
import java.util.*;
class Solution {
public int maxDistance(int[] position, int m) {
Arrays.sort(position);
int lo = 1, hi = position[position.length - 1] - position[0];
while (lo < hi) {
int mid = lo + (hi - lo + 1) / 2; // upper mid: we're finding the last true
if (canPlace(position, m, mid)) lo = mid;
else hi = mid - 1;
}
return lo;
}
private boolean canPlace(int[] pos, int m, int d) {
int count = 1, last = pos[0];
for (int i = 1; i < pos.length && count < m; i++) {
if (pos[i] - last >= d) {
count++;
last = pos[i];
}
}
return count >= m;
}
}!Common mistake
Searching for the first feasible value (lower bound) when you need the last feasible one — use mid = (lo + hi + 1) / 2 with lo = mid.
- Time: O(n log n + n log R).
- Space: O(1) besides sorting.