Magnetic Force Between Two Balls: Binary Search on Answer

You are given an array position where position[i] is the location of the ith basket, and an integer m representing the number of balls you need to place. You want to distribute the m balls into the baskets such that the minimum magnetic force (distance) between any two balls is maximized. Return that maximum possible minimum force.

This is LeetCode 1552: Magnetic Force Between Two Balls, and it is one of the cleanest examples of the "binary search on the answer" pattern. Instead of searching an array for a target, you search a range of possible distances to find the largest one that still allows a valid placement.

Why this problem matters

Binary search on the answer is one of the most powerful patterns in algorithm interviews. Once you recognize that a problem has a monotonic feasibility condition over a range of candidate answers, you can apply binary search to find the optimal value in O(log n) time. This same technique shows up in Koko Eating Bananas, Capacity to Ship Packages Within D Days, and Split Array Largest Sum.

Magnetic Force Between Two Balls is a great drill for this pattern because the "maximize the minimum" framing makes the binary search direction clear. You are looking for the largest force that is still feasible, not the smallest. Understanding both directions of the binary search on answer pattern (minimize the maximum, maximize the minimum) gives you full coverage.

The key insight

Instead of trying all possible placements of m balls across the positions, you flip the question. Pick a candidate minimum force d and ask: "Can I place m balls such that every pair is at least distance d apart?"

If the answer is yes for d, it is also yes for any smaller distance. If the answer is no for d, it is also no for any larger distance. That is a monotonic condition, and it means binary search will find the boundary.

The greedy check is simple: sort the positions, place the first ball at the leftmost position, then scan left to right and place a ball whenever the gap from the last placed ball is at least d. If you place m or more balls, the force is feasible.

The solution

def max_distance(position: list[int], m: int) -> int:
    position.sort()
    lo, hi = 1, position[-1] - position[0]

    while lo < hi:
        mid = lo + (hi - lo + 1) // 2
        count = 1
        last = position[0]
        for p in position:
            if p - last >= mid:
                count += 1
                last = p
        if count >= m:
            lo = mid
        else:
            hi = mid - 1

    return lo

Let's walk through what each piece does.

Sorting comes first. The greedy placement only works on sorted positions because you need to scan left to right and greedily pick the next position that is far enough from the last ball.

lo = 1, hi = position[-1] - position[0]. The smallest possible force is 1 (two adjacent positions). The largest possible force is the gap between the smallest and largest positions. The answer lives somewhere in this range.

mid = lo + (hi - lo + 1) // 2. This is the upper-mid formula. Because we move lo = mid (not lo = mid + 1) when the check succeeds, using the standard lower-mid formula would cause an infinite loop when lo + 1 == hi. The + 1 in the numerator avoids that.

The greedy check. Start with one ball at position[0]. Scan through the sorted positions. Whenever the current position is at least mid away from the last placed ball, place another ball there. If you end up with m or more balls, the force is achievable.

if count >= m: lo = mid. If the force works, it might be the answer, or an even larger force might also work. Keep mid in the range and search right.

else: hi = mid - 1. If the force does not work, you need something strictly smaller. Move hi below mid.

Return lo. When the loop ends, lo == hi and that is the maximum feasible force.

Visual walkthrough

Let's trace the binary search for position = [1, 2, 3, 4, 7] and m = 3. After sorting, the search range is [1, 6].

Four iterations. Instead of checking all possible placements of 3 balls across 5 positions, we tested just a few candidate distances and converged on the answer. With larger inputs, binary search still finishes in about 30 iterations regardless of the range size.

Complexity analysis

Time is O(n log n + n log D), where n is the number of positions and D is position[-1] - position[0]. Sorting takes O(n log n). The binary search runs O(log D) iterations, and each iteration scans all n positions for the greedy check. In practice, O(n log D) dominates when D is large.

Space is O(1) extra beyond the space needed for sorting. The greedy check uses only a counter and a variable to track the last placed position.

The building blocks

1. Binary search on the answer (maximize variant)

The template for "find the largest value that satisfies a condition":

lo, hi = min_possible, max_possible

while lo < hi:
    mid = lo + (hi - lo + 1) // 2
    if is_feasible(mid):
        lo = mid
    else:
        hi = mid - 1

return lo

This is the mirror image of the "minimize" template used in Koko Eating Bananas. The key difference is the upper-mid calculation and the lo = mid update. You will reuse this template in any problem that asks you to maximize the minimum of something: placing routers to maximize the weakest signal, spacing plants to maximize the closest gap, or distributing tasks to maximize the lightest load.

2. Greedy placement validation

The pattern of checking feasibility by greedily placing items left to right:

count = 1
last = position[0]
for p in position:
    if p - last >= required_gap:
        count += 1
        last = p
return count >= m

This greedy scan proves that a given gap is achievable without constructing all possible placements. It works because sorting guarantees that placing a ball at the earliest valid position never makes future placements harder. You see this same greedy validation in problems like placing flowers in a flowerbed, assigning cookies to children, or spacing frequency characters.

Edge cases

Before submitting, think through these scenarios:

• m == 2: You only need two balls. Place them at the first and last sorted positions. The answer is position[-1] - position[0].
• m == n (balls equal positions): Every position gets a ball. The answer is the minimum gap between consecutive sorted positions.
• All positions equally spaced: position = [1, 3, 5, 7], m = 3. The answer is the spacing itself (2 in this case) if it divides evenly, otherwise the floor.
• Two positions very far apart: position = [1, 1000000000], m = 2. Answer is 999999999. Binary search handles large ranges gracefully because O(log D) is about 30 steps.
• Positions with duplicates: The problem guarantees distinct positions, but if they were not distinct, two balls at the same position would have force 0.

From understanding to recall

You have seen how binary search on the answer works for maximizing the minimum force. Sort the positions, binary search the distance range, and greedily check feasibility at each midpoint. The code is about 12 lines.

But the details that matter are exactly the ones that slip away. Is it lo = mid or lo = mid + 1? Do you use upper-mid or lower-mid? Where do you place the first ball in the greedy check? These are not conceptual questions. They are recall questions, and getting them wrong in an interview means a failing solution that "almost works."

Spaced repetition closes the gap. You write the binary search template and the greedy check from scratch today, then again in two days, then in a week. After a few rounds, the lo = mid with upper-mid pattern for maximize problems is second nature. You see "maximize the minimum" in a problem description and the code flows without hesitation.

Related posts

• Koko Eating Bananas - The classic binary search on the answer problem, using the "minimize" variant
• Capacity to Ship Packages Within D Days - Another minimize variant where you binary search the ship capacity
• Split Array Largest Sum - Binary search on the maximum subarray sum, combining the same template with a different feasibility check

CodeBricks breaks Magnetic Force Between Two Balls into its binary search on answer template and greedy validation building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a "maximize the minimum" problem shows up in your interview, you do not think about it. You just write it.