Back to main article
LC 1552 Last True Medium

Magnetic Force Between Two Balls

Maximise the minimum distance. The Last True pattern on a feasibility check — and a great example of how "maximise X" problems flip to binary search.

Problem

What are we solving?

Problem Statement

You have n baskets positioned along a number line at positions position[i]. You want to place m balls into the baskets such that the minimum magnetic force (minimum distance between any two balls) is maximised. Return that maximum minimum distance.

Example
Input:position = [1,2,3,4,7], m = 3
Output:3
Explanation:Place at [1,4,7] — minimum distance is 3.
Intuition

"Maximise the minimum" = Last True

Problems that ask "maximise the minimum X" are almost always Last True binary search. The key reframe:

Instead of asking "what is the optimal placement?", ask: "given a minimum distance D, can we place all m balls with at least D apart?" Binary search on D, find the largest D where the answer is yes.

position=[1,2,3,4,7], m=3 · search space: distance 1..6
condition: canPlace(m balls, min distance D)
D=1T
D=2T
D=3T*
D=4F
D=5F
D=6F
Last T = D=3. Place balls at [1,4,7]: gaps are 3 and 3. Maximum minimum distance = 3. ✓

The feasibility check

Sort the positions first. Then greedily place balls: put the first ball at the leftmost position. For each subsequent position, only place a ball there if it is at least D away from the last placed ball. If we can place all m balls this way, D is feasible.

→

Sort first! The problem doesn't guarantee positions are sorted. Sorting takes O(n log n) but is required for the greedy placement check to work correctly.

→

Pattern recognition: "Maximise the minimum" → Last True. "Minimise the maximum" → First True (like LC 410 Split Array). These two phrasings are mirrors of each other and both binary search the answer space.

Step-by-step walkthrough

position = [1,2,3,4,7] (sorted), m=3, checking D=3

1
Place ball 1 at position 1 (always place at first position)

Last placed = 1. Balls placed = 1.

2
Position 2: distance from last = 2-1 = 1 < 3

Too close. Skip.

3
Position 3: distance from last = 3-1 = 2 < 3

Too close. Skip.

4
Position 4: distance from last = 4-1 = 3 ≥ 3

Place ball 2 here. Last placed = 4. Balls placed = 2.

5
Position 7: distance from last = 7-4 = 3 ≥ 3

Place ball 3 here. Balls placed = 3 = m. D=3 is feasible! ✓

Solution

Clean implementation

class Solution {
    public int maxDistance(int[] position, int m) {
        Arrays.sort(position);
        int n = position.length;

        int left = 1;
        int right = position[n - 1] - position[0]; // max possible distance
        int boundary = 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (canPlace(position, m, mid)) {
                // feasible — save and try a larger minimum distance
                boundary = mid;
                left = mid + 1;
            } else {
                // not feasible — try a smaller distance
                right = mid - 1;
            }
        }

        return boundary;
    }

    private boolean canPlace(int[] pos, int m, int minDist) {
        int count = 1;          // place first ball at pos[0]
        int lastPlaced = pos[0];

        for (int i = 1; i < pos.length; i++) {
            if (pos[i] - lastPlaced >= minDist) {
                count++;
                lastPlaced = pos[i];
                if (count == m) return true; // placed all balls
            }
        }
        return count >= m;
    }
}
class Solution:
    def maxDistance(self, position: list[int], m: int) -> int:
        position.sort()
        left = 1
        right = position[-1] - position[0]  # max possible distance
        boundary = 1

        while left <= right:
            mid = left + (right - left) // 2

            if self.can_place(position, m, mid):
                # feasible — save and try a larger minimum distance
                boundary = mid
                left = mid + 1
            else:
                # not feasible — try a smaller distance
                right = mid - 1

        return boundary

    def can_place(self, pos, m, min_dist):
        count, last = 1, pos[0]  # first ball always at pos[0]
        for p in pos[1:]:
            if p - last >= min_dist:
                count += 1
                last = p
                if count == m:
                    return True
        return count >= m

Complexity

Time
O(n log D)
Sort is O(n log n). Binary search is O(log D) where D = max position. Each feasibility check is O(n).
Space
O(1)
Constant extra space beyond the input sort (in-place).
!

Common mistake — forgetting to sort: The greedy placement only works on sorted positions. If you forget to sort first, the feasibility check produces wrong answers and the binary search converges to a wrong result with no error.

↑ Pattern map