Problem

In the universe Earth C-137, Rick discovered a special form of magnetic force between two balls if they are put in his new invented basket. Rick has n empty baskets, the ith basket is at position[i], Morty has m balls and needs to distribute the balls into the baskets such that the minimum magnetic force between any two balls is maximum.

Rick stated that magnetic force between two different balls at positions x and y is |x - y|.

Given the integer array position and the integer m. Return the required force.

Examples

Example 1:


<- Force = 3 -><- Force = 3 ->
[🏐] [~] [~] [🏐] [~]  [~] [🏐]
  1   2   3   4    5    6   7

[ 🏐 ] = basket with ball
[~] = empty baskets

Input: position = [1,2,3,4,7], m = 3
Output: 3
Explanation: Distributing the 3 balls into baskets 1, 4 and 7 will make the magnetic force between ball pairs [3, 3, 6]. The minimum magnetic force is 3. We cannot achieve a larger minimum magnetic force than 3.

Example 2:

Input: position = [5,4,3,2,1,1000000000], m = 2
Output: 999999999
Explanation: We can use baskets 1 and 1000000000.

Solution

The problem is to distribute m balls into n baskets such that the minimum magnetic force between any two balls is maximized. The idea is to determine the maximum possible minimum distance between any two balls when they are placed in the baskets.

Method 1 - Binary Search

Lets take inputs position = [1,2,3,4,7], m = 3, these are the steps we can follow:

  1. Sort the Positions: First, sort the baskets’ positions. position = [1,2,3,4,7]
  2. Binary Search on the Answer: Use binary search to find the maximum possible minimum force.
    • The lower bound lo is 1 ⇨ min possible force
    • The upper bound hi is (position[n - 1] - position[0]) / (m - 1) ⇨ max possible force. Using example, hi = (7 - 1)/2 = 3. We divide by m-1, because the force happens between 2 adjacent balls, hence for m balls, we will have m - 1 forces as per above question.
  3. Greedy Check: For each mid value in the binary search, use a greedy algorithm to check if it’s possible to place the m balls such that the minimum distance between any two balls is at least mid. Lets see how:
    1. Iteration 1: low = 1, high = 3 ⇨ mid = 4 / 2 = 2. Now, we try to keep m = 3 balls, such that distance between these force is minForce = 2.
      • Keep first ball at position 1, then we keep 2nd ball at position 3 which has, and then we keep 7.
      • Since we managed to keep the balls with minForce = 2, lets try to maximize it a bit. So, low = mid + 1 = 3
    2. Iteration 2: low = 3, high = 3 ⇨ mid = 3. Now, we try to keep m = 3 balls, such that distance between these force is minForce = 3.
      • Keep first ball at position 1, then we keep 2nd ball at position 4, and then third ball at position 7.
      • Since we managed to keep the balls with minForce = 3, lets try to maximize it a bit. So, low = mid + 1 = 4
    3. Now, low > mid, hence we come out of the loop, and minForce = 3.

Code

Java
public class Solution {
	public int maxDistance(int[] position, int m) {
		// Sort the positions of the baskets
		Arrays.sort(position);

		int n = position.length;
		int low = 1; // Minimum possible force
		int high = (position[n - 1] - position[0]) / (m - 1); // Maximum possible force
		while (low <= high) {
			int mid = low + (high - low) / 2;

			if (canPlaceBalls(position, m, mid)) {
				low = mid + 1; // Try for a larger minimum force
			} else {
				high = mid - 1; // Try for a smaller minimum force
			}
		}

		return high;
	}

	private boolean canPlaceBalls(int[] position, int m, int minForce) {
		int count = 1; // Place the first ball
		int lastPosition = position[0];

		for (int i = 1; i < position.length; i++) {
			if (position[i] - lastPosition >= minForce) {
				count++;
				lastPosition = position[i];

				if (count == m) {
					return true;
				}
			}
		}

		return false;
	}
}

Complexity

  • ⏰ Time complexity: O(n * log (max - min)), where n is the number of baskets and (max - min) is the range of positions.
  • 🧺 Space complexity: O(1)