Magnetic Force Between Two Balls — Solution

Problem

You have n baskets arranged along a line at positions given in an array. Place exactly m balls into m distinct baskets so that the minimum magnetic force between any two balls (which equals the distance between their baskets) is as large as possible.

• Input: position = [1, 2, 3, 4, 7], m = 3
• Output: 3
• Explanation: Place balls at positions 1, 4, and 7 — the gaps are 3, 3, and 6, so the minimum force is 3.

A counter-example to show why greedy placement without binary search doesn't work: placing balls at 1, 2, 7 gives a minimum force of only 1, which is far from optimal.

Intuition

The answer is monotonic: if we can guarantee a minimum distance of d between all balls, then any smaller minimum distance is also achievable. This monotonicity means we can binary search on the answer itself. For any candidate minimum distance d, we sort the baskets and greedily place each ball at the earliest basket that is at least d away from the previous ball — if this greedy scan places all m balls, then d is feasible.

Solution — Binary Search on Answer

Sort the basket positions, then binary search over the candidate minimum distance. For each midpoint distance, run a greedy left-to-right scan to count how many balls can be placed with at least that spacing. Maximize the largest feasible distance.

1. Sort position so baskets are in order.
2. Set binary search bounds: left = 1, right = position[-1] - position[0].
3. At each midpoint mid, run can_place(mid): start at position[0], scan right, and place a ball whenever the gap from the last placed ball is ≥ mid.
4. If can_place(mid) returns true, record mid as a valid answer and search the upper half for a larger feasible distance.
5. If false, search the lower half.
6. Return the largest feasible distance found.

1def maxDistance(position: list[int], m: int) -> int:
2    position.sort()
3
4    def can_place(min_force: int) -> bool:
5        balls_placed = 1
6        last_position = position[0]  # always place first ball at the leftmost basket
7
8        for i in range(1, len(position)):
9            if position[i] - last_position >= min_force:  # gap is large enough
10                balls_placed += 1
11                last_position = position[i]
12                if balls_placed == m:  # early exit once all balls are placed
13                    return True
14
15        return balls_placed >= m
16
17    left, right = 1, position[-1] - position[0]
18    result = 0
19
20    while left <= right:
21        mid = (left + right) // 2
22        if can_place(mid):
23            result = mid      # mid is feasible; try to do better
24            left = mid + 1
25        else:
26            right = mid - 1   # mid is too large; reduce the target distance
27
28    return result

Time: O(n log n + n log W) where W = max position − min position (up to 10⁹) — sorting takes O(n log n) and the binary search runs O(log W) greedy scans each costing O(n).

Space: O(log n) — only the call stack used by sorting; no auxiliary data structures.

Complexity Summary

Common Mistakes

• Forgetting to sort positions — the greedy scan assumes positions are in ascending order; without sorting, you'll get wrong ball counts even for simple inputs.
• Using > instead of >= in the gap check — the problem asks for minimum force of at least d, so position[i] - lastPosition >= minForce is correct; > would reject valid placements.
• Wrong upper bound for binary search — searching up to position[-1] instead of position[-1] - position[0] wastes iterations but doesn't break correctness; knowing the tight bound prevents confusion.
• Not saving result separately — if you try to derive the answer as left - 1 after the loop, you need to verify the loop exits with left one past the last feasible value; tracking result explicitly is safer and clearer.
• Skipping the early exit inside can_place — once balls_placed == m, returning immediately avoids unnecessary scanning; omitting it is a performance issue, not a correctness bug, but it's a detail interviewers notice.

Related Problems

• capacity-to-ship-packages-within-d-days — same binary-search-on-answer template, minimizing maximum load instead of maximizing minimum distance
• koko-eating-bananas — binary search on the eating speed, greedy feasibility check per candidate
• split-array-largest-sum — minimize the maximum subarray sum using the same feasibility-check pattern
• find-minimum-in-rotated-sorted-array — pure binary search on a sorted structure; builds the same left/right convergence intuition
• single-element-in-a-sorted-array — binary search on parity of indices, reinforcing that binary search applies beyond simple sorted lookups