Magnetic Force Between Two Balls

Magnetic Force Between Two Balls

What is this problem about?

In the Magnetic Force Between Two Balls problem, you are given an array of positions representing empty baskets along a line, and an integer m representing the number of magnetic balls. You need to place all m balls into the baskets such that the minimum magnetic force between any two balls is maximized. The force between a ball at position x and y is simply |x - y|.

Why is this asked in interviews?

This is a textbook "Minimize the Maximum" or "Maximize the Minimum" optimization problem. It is a favorite among top-tier tech companies because it tests your ability to recognize when to apply Binary Search on the Answer. It forces you to transition from asking "How do I place these balls optimally?" to "If I guess a specific force, can I successfully place all the balls?"

Algorithmic pattern used

The absolute optimal pattern here is Binary Search on the Answer. First, sort the position array. Then, define a search space for the possible minimum force: from 1 (balls in adjacent baskets) to max_position - min_position (balls at extreme ends). For a guessed mid-point force F, use a Greedy approach to see if you can place all m balls such that every pair is at least F distance apart. If you can, search higher; if you can't, search lower.

Example explanation

Positions: [1, 2, 3, 4, 7], m = 3 balls. Sorted positions: [1, 2, 3, 4, 7]. Let's binary search the force. Max possible force is $7 - 1 = 6$. Midpoint force $F = 3$. Can we place 3 balls with at least 3 distance?

• Ball 1 goes at 1.
• Next valid basket must be $\ge 1 + 3 = 4$. Basket 4 is valid. Ball 2 goes at 4.
• Next valid basket must be $\ge 4 + 3 = 7$. Basket 7 is valid. Ball 3 goes at 7. We successfully placed all 3 balls with a minimum distance of 3! We can now try to search for an even larger force (e.g., 4). It will fail, leaving 3 as our maximum possible minimum force.

Common mistakes candidates make

A very common mistake is trying to solve this using Dynamic Programming, which is overly complex and usually results in a Time Limit Exceeded error. Another mistake is forgetting to sort the array of basket positions initially. The greedy placement logic strictly requires the baskets to be evaluated in ascending order to simulate walking down the physical line.

Interview preparation tip

When tackling the Magnetic Force Between Two Balls coding problem, internalize the phrasing "maximize the minimum." This phrase is a massive neon sign pointing to Binary Search. Practice writing the greedy canPlace(m, force) helper function; it is incredibly simple (just loop and check if current_position - last_placed_position >= force) and forms the core of many similar problems like 'Allocate Books' or 'Koko Eating Bananas'.