Magnetic Force Between Two Balls
Understanding the Problem
We have baskets at various positions along a number line, and we need to place m balls into m of these baskets. The "magnetic force" between any two balls is the absolute distance between their basket positions. Among all pairs of placed balls, there will be some pair that is closest together, and that pair defines the minimum force. Our goal is to choose positions so that this minimum force is as large as possible.
This is the same shape as placing cell towers along a highway. You spread them as far apart as possible so coverage is even, and the limiting factor is the two towers closest together. Maximizing the smallest gap is the goal.
Rather than searching for the optimal set of positions directly, we can invert the question: given a candidate minimum distance d, can we place all m balls so that every pair is at least d apart? Answering that yes/no question efficiently lets us find the largest d for which the answer is yes, which is a binary-search-on-the-answer setup.
Key Constraints:
2 <= n <= 10^5--> We can afford O(n log n) for sorting and O(n) per feasibility check. An O(n^2) approach per check would be borderline.1 <= position[i] <= 10^9--> Positions can be up to a billion, so the search space for the answer is large. Linear scanning of all possible distances would be too slow. Binary search over this range is O(log(10^9)) which is about 30 iterations.2 <= m <= n--> We always have at least 2 balls, and there are enough baskets for all balls.
Approach 1: Brute Force (Linear Scan of All Distances)
Intuition
Try every possible minimum distance value, starting from the largest and working downward. For each candidate distance d, check whether all m balls can be placed so that every consecutive pair is at least d apart. The first d that works is the answer, because we scan from the top.
The feasibility check needs a sorted array. Place the first ball in the leftmost basket, then for each subsequent ball, place it in the next basket that is at least d away from the last placed ball. If all m balls fit this way, the distance d is feasible.
The greedy check is O(n), but scanning all distances from the maximum gap down to 1 is up to 10^9 iterations in the worst case, which is what makes this approach slow.
Algorithm
- Sort the
positionarray. - Compute
maxDistance = position[n - 1] - position[0]. - For
dfrommaxDistancedown to 1: - Run the greedy feasibility check: place the first ball at
position[0], then greedily place each next ball at the first position that is at leastdaway from the last placed ball. - If all
mballs can be placed, returnd. - Return 1 (the minimum distance is always achievable with at least 2 positions).
Visualization and Code
Loading animation...
- Time Complexity: O(n log n + n * D) where D = max position - min position. Sorting takes O(n log n). Then for each candidate distance from D down to 1, we run a greedy check that is O(n). In the worst case, D can be up to 10^9, making this far too slow.
- Space Complexity: O(1) extra space beyond sorting. The greedy check uses only a few variables.
The feasibility function is monotonic: if distance d works, so does anything smaller. That property lets us binary search for the threshold instead of scanning every distance.
Approach 2: Binary Search on Answer (Optimal)
Intuition
The greedy placement check from the brute force stays the same. The only change is how we choose which distances to test: binary search instead of a linear scan.
The feasibility function is monotonic. If m balls fit with a minimum gap of d, the same positions also satisfy a minimum gap of d - 1. Conversely, if m balls do not fit with a minimum gap of d, they cannot fit with a gap of d + 1 either. There is a threshold value where all distances at or below it are feasible and all distances above it are not. Binary search finds this threshold in O(log D) iterations.
For each candidate midpoint, the greedy check is the same: place the first ball at the leftmost basket, then place each subsequent ball at the next basket that is at least mid away from the last placed one. If we place all m balls, the distance is feasible.
The greedy placement is optimal for the feasibility check by an exchange argument. Suppose some valid placement for distance d exists. Sort its chosen positions. The greedy strategy places its first ball at position[0], which is at or to the left of the valid placement's first ball, so by induction each greedy ball sits at or to the left of the corresponding valid ball. Sitting further left only leaves more room for the next ball, so if the valid placement fits all m balls, the greedy one fits at least as many. Therefore greedy succeeds whenever any placement succeeds.
Combined with monotonicity (all d at or below the answer are feasible, all above are not), the threshold is well defined and binary search converges to it.
Algorithm
- Sort the
positionarray. - Set
low = 1andhigh = position[n - 1] - position[0]. - While
low <= high: - Compute
mid = low + (high - low) / 2. - Run the greedy feasibility check with minimum distance
mid. - If feasible (can place all
mballs), the answer is at leastmid. Setresult = midand search higher:low = mid + 1. - If not feasible, the distance is too large. Search lower:
high = mid - 1. - Return
result.
Visualization and Code
Loading animation...
- Time Complexity: O(n log n + n log D) where D = max position - min position. Sorting is O(n log n). The binary search runs O(log D) iterations (about 30 for D up to 10^9), and each iteration does an O(n) greedy scan.
- Space Complexity: O(1) extra space beyond sorting. The binary search and greedy check use only a few integer variables.