Magnetic Force Between Two Balls — Maximize Minimum Distance [LC 1552, Google]

Problem Statement#

You have n baskets at positions position[]. Place m balls such that the minimum magnetic force (distance) between any two balls is maximized. Return the maximum achievable minimum distance.

Constraints:

• 2 <= n <= 10^5
• 1 <= m <= n
• 0 <= position[i] <= 10^9
• All positions are distinct

Input:  position = [1,2,3,4,7], m = 3
Output: 3

Input:  position = [5,4,3,2,1,1000000000], m = 2
Output: 999999999

Why This Problem Matters#

LC 1552 is the canonical "maximize the minimum" binary search problem, the mirror image of "minimize the maximum" problems like Koko Eating Bananas. Google and Amazon ask it to test whether candidates can flip their thinking from minimisation to maximisation while keeping the same binary search template.

The maximise-minimum pattern appears throughout interview problem sets: aggressive cows (classic competitive programming), placing charging stations, splitting arrays. Recognising the pattern and adjusting the template (upper-mid, lo = mid on success) is the key skill this problem trains.

The Core Insight#

Binary search on the minimum distance d in [1, (max_pos - min_pos) / (m - 1)]. For a given d, greedily place balls: always place the next ball at the earliest basket that is at least d away from the previous ball. If you can place all m balls this way, d is feasible.

For maximisation, the template flips:

• If feasible(mid): the minimum distance could be larger, so lo = mid (keep mid as a candidate).
• If not feasible(mid): mid is too large, so hi = mid - 1.
• Use upper-mid (lo + hi + 1) // 2 to prevent infinite loops when lo = mid is used.

Visual Dry Run#

Input: position = [1,2,3,4,7], m = 3

After sort: [1,2,3,4,7]. Bounds: lo=1, hi=(7-1)//(3-1)=3

Solution (Optimal)#

class Solution:
    def maxDistance(self, position: list[int], m: int) -> int:
        position.sort()
 
        def feasible(gap: int) -> bool:
            count = 1
            prev = position[0]
            for p in position[1:]:
                if p - prev >= gap:
                    count += 1
                    prev = p
                    if count == m:
                        return True
            return count >= m
 
        lo = 1
        hi = (position[-1] - position[0]) // (m - 1)
 
        while lo < hi:
            mid = lo + (hi - lo + 1) // 2  # upper-mid for maximisation
            if feasible(mid):
                lo = mid       # mid is feasible; try larger
            else:
                hi = mid - 1   # mid is too large; shrink upper bound
 
        return lo

var maxDistance = function(position, m) {
    position.sort((a, b) => a - b);
 
    function feasible(gap) {
        let count = 1;
        let prev = position[0];
        for (let i = 1; i < position.length; i++) {
            if (position[i] - prev >= gap) {
                count++;
                prev = position[i];
                if (count === m) return true;
            }
        }
        return count >= m;
    }
 
    let lo = 1;
    let hi = Math.floor((position[position.length - 1] - position[0]) / (m - 1));
 
    while (lo < hi) {
        const mid = lo + Math.floor((hi - lo + 1) / 2); // upper-mid
        if (feasible(mid)) lo = mid;
        else hi = mid - 1;
    }
 
    return lo;
};

Time: O(n log(max_gap)) — O(log D) binary search iterations, each O(n) feasibility check Space: O(1) — only pointer variables (sorting is in-place)

Common Mistakes#

• Using lower-mid (lo + hi) // 2 with lo = mid — causes infinite loop when lo + 1 == hi.
• Setting hi = position[-1] - position[0] — valid but unnecessarily large upper bound; (max - min) / (m - 1) is tighter.
• Not sorting positions — the greedy placement only works in sorted order.
• Using lo = mid + 1 instead of lo = mid on success — this skips the feasible answer.
• Confusing this with minimisation (which uses lower-mid and hi = mid on success) — maximisation uses upper-mid and lo = mid on success.

Interview Tips#

• Explicitly state whether you are minimising or maximising before writing code — they use different mid formulas.
• The greedy check is: sort positions, place a ball at the first position, then each subsequent ball at the earliest position at least gap away.
• Tighten the upper bound to (max - min) // (m - 1) — it makes the binary search start closer to the answer and shows careful reasoning.
• This is the "aggressive cows" problem from competitive programming — mention this if the interviewer seems interested.

Follow-up Questions#

• LC 410 (Split Array Largest Sum): The minimise-maximum mirror image — binary search on maximum subarray sum, greedy check on number of splits.
• Aggressive Cows (SPOJ): The same problem by a different name.
• What if positions are not distinct? Deduplicate first; duplicate positions would allow zero-distance placements which breaks the minimum gap logic.
• What if m == 1? Only one ball, minimum distance is vacuously 0 (or undefined). The greedy check handles it trivially.
• LC 2616 (Minimize the Maximum Difference of Pairs): Same pattern in minimisation direction.

Key Takeaways#

• LC 1552 is the canonical "maximize the minimum" binary search problem, the direct counterpart of minimise-maximum problems like LC 875 and LC 1011.
• For maximisation: use upper-mid (lo + hi + 1) // 2 and set lo = mid on feasibility — this prevents infinite loops when lo + 1 == hi.
• The feasibility check is a greedy O(n) scan: sort positions, place balls greedily at the earliest valid position at each step.
• Search bounds: lo = 1 (minimum possible gap), hi = (max - min) // (m - 1) (maximum even spread across all m balls).
• Sorting the positions is mandatory before any greedy placement or binary search reasoning.
• The maximise-minimum pattern appears in: aggressive cows, placing sensors, splitting arrays, distributing items — recognising it is the key skill.
• Google and Amazon ask this problem to test whether candidates can adapt the standard binary search template to maximisation without confusion.