Problem Description

The "Magnetic Force Between Two Balls" problem asks you to arrange m balls in n baskets positioned along a line, such that the minimum magnetic force (the distance between any two balls) is as large as possible.

You are given an array position of length n, where position[i] is the location of the i-th basket. You need to choose m baskets to place the balls, with exactly one ball per chosen basket.

The magnetic force between any two balls is the absolute difference between their basket positions. Your goal is to maximize the minimum magnetic force between any two balls.

Constraints:

• 1 <= m <= n <= 10⁵
• 0 <= position[i] <= 10⁹
• All basket positions are distinct
• There is always at least one valid way to place the balls

Thought Process

At first glance, one might think about checking all possible ways to place m balls in n baskets and then calculating the minimum distance for each configuration. However, this approach would be computationally infeasible due to the enormous number of combinations, especially with large input sizes.

Instead, we can reframe the problem: for a given minimum distance d, can we place all m balls such that every pair is at least d apart? If we can check this efficiently, we can use binary search to find the largest possible d.

This shift from "searching for a configuration" to "searching for the maximum feasible minimum distance" is the key insight. It allows us to use binary search on the answer, which is a common technique for optimization problems with a monotonic property.

Solution Approach

We use a binary search approach to maximize the minimum magnetic force:

• Step 1: Sort the basket positions.
  Sorting ensures we can efficiently check distances between baskets.
• Step 2: Define the search range for magnetic force.
  The smallest possible force is 1 (since positions are distinct), and the largest is the distance between the most distant baskets.
• Step 3: Binary search for the answer.
  • For each candidate minimum force mid, check if it's possible to place all m balls such that the distance between any two is at least mid.
  • This is done greedily: start with the first basket, and for each next basket, place a ball only if it's at least mid away from the last placed ball. Count how many balls you can place.
  • If you can place all m balls, try a larger force (move the binary search right); otherwise, try a smaller force (move left).
• Step 4: Return the largest feasible minimum force.

This approach is efficient because the greedy check is linear in the number of baskets, and binary search reduces the number of candidate forces to logarithmic scale.

Example Walkthrough

Example:
position = [1, 2, 8, 4, 9], m = 3

1. Sort positions: [1, 2, 4, 8, 9]
2. Set binary search range: left = 1, right = 8 (9 - 1)
3. First mid = 4:
   • Place first ball at 1
   • Next possible at 4 (since 4 - 1 >= 4)? No, 2 - 1 = 1, 4 - 1 = 3 (not enough). Next is 8 (8 - 1 = 7 >= 4), place second ball at 8
   • Next is 9 (9 - 8 = 1), not enough. Done. Only 2 balls placed. So 4 is too large.
   • Decrease right to 3.
4. Next mid = 2:
   • Place at 1
   • 2 - 1 = 1 (not enough), 4 - 1 = 3 (≥2), place at 4
   • 8 - 4 = 4 (≥2), place at 8
   • Placed 3 balls. Success!
   • Try higher: left = 3
5. Next mid = 3:
   • Place at 1
   • 2 - 1 = 1 (not enough), 4 - 1 = 3 (≥3), place at 4
   • 8 - 4 = 4 (≥3), place at 8
   • Placed 3 balls. Success!
   • Try higher: left = 4
6. End: left > right, so the answer is 3.

Thus, the largest minimum magnetic force possible is 3.

Time and Space Complexity

• Brute-force approach:
  Try all combinations of m baskets from n (which is O(n^m)), and for each, compute the minimum distance. This is not feasible for large n.
• Optimized (binary search + greedy):
  • Sorting: O(n \log n)
  • Binary search: O(\log D) iterations, where D is the max possible distance (up to 10⁹)
  • Each greedy check: O(n)
  • Total: O(n \log n + n \log D)
  • Space: O(1) extra (if sorting in place), or O(n) if making a copy.

Summary

The "Magnetic Force Between Two Balls" problem is cleverly solved by reframing it as a search for the largest feasible minimum distance, rather than brute-forcing all arrangements. By combining binary search with a greedy placement check, we achieve an elegant and efficient solution that scales to large inputs. The key insight is recognizing the monotonic relationship between the minimum force and the possibility of placing all balls, allowing binary search to quickly zero in on the optimal answer.

Code Implementation

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        left, right = 1, position[-1] - position[0]
        answer = 0

        def can_place(force):
            count = 1
            last = position[0]
            for pos in position[1:]:
                if pos - last >= force:
                    count += 1
                    last = pos
                    if count == m:
                        return True
            return False

        while left <= right:
            mid = (left + right) // 2
            if can_place(mid):
                answer = mid
                left = mid + 1
            else:
                right = mid - 1
        return answer
      

class Solution {
public:
    int maxDistance(vector<int>& position, int m) {
        sort(position.begin(), position.end());
        int left = 1, right = position.back() - position.front(), answer = 0;

        auto can_place = [&](int force) {
            int count = 1, last = position[0];
            for (int i = 1; i < position.size(); ++i) {
                if (position[i] - last >= force) {
                    count++;
                    last = position[i];
                    if (count == m) return true;
                }
            }
            return false;
        };

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (can_place(mid)) {
                answer = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return answer;
    }
};
      

class Solution {
    public int maxDistance(int[] position, int m) {
        Arrays.sort(position);
        int left = 1, right = position[position.length - 1] - position[0];
        int answer = 0;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (canPlace(position, m, mid)) {
                answer = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return answer;
    }

    private boolean canPlace(int[] position, int m, int force) {
        int count = 1, last = position[0];
        for (int i = 1; i < position.length; i++) {
            if (position[i] - last >= force) {
                count++;
                last = position[i];
                if (count == m) return true;
            }
        }
        return false;
    }
}
      

var maxDistance = function(position, m) {
    position.sort((a, b) => a - b);
    let left = 1, right = position[position.length - 1] - position[0];
    let answer = 0;

    function canPlace(force) {
        let count = 1, last = position[0];
        for (let i = 1; i < position.length; i++) {
            if (position[i] - last >= force) {
                count++;
                last = position[i];
                if (count === m) return true;
            }
        }
        return false;
    }

    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (canPlace(mid)) {
            answer = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return answer;
};