# Magnetic Force Between Two Balls
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/magnetic-force-between-two-balls)
Canonical: https://scaleengineer.com/dsa/problems/magnetic-force-between-two-balls
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Roblox](https://scaleengineer.com/companies/roblox), [PhonePe](https://scaleengineer.com/companies/phonepe)
---
## 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_.

**Example 1:**

![](https://assets.glich.co/dsa/magnetic-force-between-two-balls/image0.jpg) 

**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.

**Constraints:**

* `n == position.length`
* `2 <= n <= 105`
* `1 <= position[i] <= 109`
* All integers in `position` are **distinct**.
* `2 <= m <= position.length`

# Approaches
## Linear Scan on the Answer
This approach involves checking every possible value for the minimum distance, from the largest possible down to the smallest. The first distance that allows placing `m` balls is the maximum possible minimum distance. While conceptually simple, it is too slow for the given constraints.
**Time:** O(n log n + D * n), where `D` is the maximum distance (`position[n-1] - position[0]`). Sorting takes `O(n log n)`. The loop runs up to `D` times, and each call to `canPlace` takes `O(n)`. Since `D` can be up to `10^9`, this approach is too slow. · **Space:** O(log n) or O(n) for sorting, depending on the implementation. If sorting is done in-place, the space complexity is O(log n) for the recursion stack or O(1) for iterative sorts like Heapsort.
**Pros:** Conceptually simpler to understand than binary search.; Correctly identifies the problem as a search for the optimal distance.
**Cons:** Extremely inefficient due to the large search space for the distance `d`.; Will result in a 'Time Limit Exceeded' error for most competitive programming platforms due to the constraints.
### Explanation
The core idea is to transform the problem from finding a specific arrangement of balls to finding an optimal value for the minimum distance. We can test each possible distance value to see if it's feasible.

First, we sort the `position` array. This allows us to greedily check for placements. The possible values for the minimum distance `d` are in the range `[1, position[n-1] - position[0]]`.

We can iterate `d` from the maximum possible value downwards. For each `d`, we check if we can place `m` balls. To do this, we use a greedy function `canPlace(d)`:
1. Place the first ball at `position[0]`.
2. Iterate from `position[1]` onwards. Find the next basket `position[i]` such that its distance from the last placed ball is at least `d`.
3. Place a ball there and repeat until we have either placed `m` balls or run out of baskets.

If we can place `m` balls, we have found our answer because we are iterating from the largest `d` downwards. If not, we try a smaller `d`.

```java
import java.util.Arrays;

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

        for (int d = maxPossibleDist; d >= 1; d--) {
            if (canPlace(position, m, d)) {
                return d;
            }
        }
        return 0; // Should not be reached given the constraints
    }

    // Checks if we can place m balls with at least d distance apart.
    private boolean canPlace(int[] position, int m, int d) {
        int ballsPlaced = 1;
        int lastPosition = position[0];
        for (int i = 1; i < position.length; i++) {
            if (position[i] - lastPosition >= d) {
                ballsPlaced++;
                lastPosition = position[i];
            }
        }
        return ballsPlaced >= m;
    }
}
```
### Algorithm
- Sort the `position` array in ascending order.
- The maximum possible value for the minimum distance is `D = position[n-1] - position[0]`. The minimum is 1.
- We can iterate through all possible integer distances `d` from `D` down to 1.
- For each `d`, we check if it's possible to place `m` balls with at least `d` distance between them using a greedy helper function `canPlace(d)`.
- The `canPlace(d)` function works as follows:
  1. Place the first ball at `position[0]`.
  2. Iterate through the remaining positions, placing the next ball at the earliest possible spot `position[i]` that maintains the minimum distance `d` from the previously placed ball.
  3. Count the total number of balls placed. If it's at least `m`, `canPlace(d)` returns `true`.
- The first (and largest) `d` for which `canPlace(d)` returns `true` is the answer.

## Binary Search on the Answer
This approach optimizes the search for the maximum possible minimum distance by using binary search. Instead of checking every possible distance, we efficiently narrow down the search space. This is a classic technique for problems that ask to 'maximize a minimum' or 'minimize a maximum'.
**Time:** O(n log n + n log D), where `D` is the maximum distance (`position[n-1] - position[0]`). Sorting takes `O(n log n)`. The binary search runs `log D` times, and each call to `canPlace` takes `O(n)`. This is efficient enough to pass the given constraints. · **Space:** O(log n) or O(n) for sorting, depending on the implementation. If sorting is done in-place, the space complexity is O(log n) for the recursion stack or O(1) for iterative sorts like Heapsort.
**Pros:** Highly efficient due to the logarithmic reduction of the search space.; Guaranteed to find the optimal solution.; A classic and powerful technique for 'maximize the minimum' or 'minimize the maximum' type problems.
**Cons:** Slightly more complex to understand and implement than a linear scan.; Requires identifying the monotonic property of the problem to apply binary search.
### Explanation
The key insight is that the feasibility of a minimum distance `d` is monotonic. If we can place `m` balls with a minimum distance of `d`, we can certainly do so for any distance smaller than `d`. This allows us to binary search for the largest possible `d` that works.

The search range for our answer `d` will be from `1` to `position[n-1] - position[0]`. We'll call these bounds `low` and `high`.

In each step of the binary search, we take a candidate distance `mid` and check if it's possible to place `m` balls with at least this separation. This check is performed by a greedy helper function `canPlace(d)`:
1. Place the first ball at `position[0]`.
2. Iterate through the sorted positions and place the next ball at the first available basket that is at least `d` distance away from the last placed ball.
3. If we are able to place `m` or more balls, `canPlace(d)` returns `true`.

Based on the result of `canPlace(mid)`:
- If it's `true`, `mid` is a valid distance. We store it as our current best answer and try for an even larger distance by setting `low = mid + 1`.
- If it's `false`, `mid` is too large. We need to try smaller distances, so we set `high = mid - 1`.

This process continues until `low` crosses `high`, and our stored answer will be the maximum possible minimum distance.

```java
import java.util.Arrays;

class Solution {
    public int maxDistance(int[] position, int m) {
        Arrays.sort(position);
        int n = position.length;
        int low = 1;
        int high = position[n - 1] - position[0];
        int ans = 0;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (canPlace(position, m, mid)) {
                ans = mid; // This distance is possible, try for a larger one.
                low = mid + 1;
            } else {
                high = mid - 1; // This distance is not possible, try a smaller one.
            }
        }
        return ans;
    }

    // Checks if we can place m balls with at least d distance apart.
    private boolean canPlace(int[] position, int m, int d) {
        int ballsPlaced = 1;
        int lastPosition = position[0];
        for (int i = 1; i < position.length; i++) {
            if (position[i] - lastPosition >= d) {
                ballsPlaced++;
                lastPosition = position[i];
                if (ballsPlaced == m) {
                    return true;
                }
            }
        }
        return false;
    }
}
```
### Algorithm
- First, sort the `position` array in ascending order.
- The problem has a monotonic property: if a distance `d` is achievable, any distance `d' < d` is also achievable. This allows us to use binary search on the answer.
- Define a search space for the answer `d`. The lower bound `low` is 1, and the upper bound `high` is `position[n-1] - position[0]`.
- While `low <= high`:
  - Calculate the middle value `mid = low + (high - low) / 2`.
  - Use a greedy helper function `canPlace(mid)` to check if it's possible to place `m` balls with a minimum distance of at least `mid`.
  - If `canPlace(mid)` is `true`, it means `mid` is a possible answer. We try for a larger distance, so we store `mid` as a potential answer and set `low = mid + 1`.
  - If `canPlace(mid)` is `false`, `mid` is too large. We need to try a smaller distance, so we set `high = mid - 1`.
- The last valid `mid` stored is the maximum possible minimum distance.

# Solutions
### Java

```java
class Solution {
public
  int maxDistance(int[] position, int m) {
    Arrays.sort(position);
    int left = 1, right = position[position.length - 1];
    while (left < right) {
      int mid = (left + right + 1) >>> 1;
      if (check(position, mid, m)) {
        left = mid;
      } else {
        right = mid - 1;
      }
    }
    return left;
  }
private
  boolean check(int[] position, int f, int m) {
    int prev = position[0];
    int cnt = 1;
    for (int i = 1; i < position.length; ++i) {
      int curr = position[i];
      if (curr - prev >= f) {
        prev = curr;
        ++cnt;
      }
    }
    return cnt >= m;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} position * @param {number} m * @return {number} */ var maxDistance =
  function (position, m) {
    position.sort((a, b) => {
      return a - b;
    });
    let left = 1,
      right = position[position.length - 1];
    const check = function (f) {
      let prev = position[0];
      let cnt = 1;
      for (let i = 1; i < position.length; ++i) {
        const curr = position[i];
        if (curr - prev >= f) {
          prev = curr;
          ++cnt;
        }
      }
      return cnt >= m;
    };
    while (left < right) {
      const mid = (left + right + 1) >> 1;
      if (check(mid)) {
        left = mid;
      } else {
        right = mid - 1;
      }
    }
    return left;
  };

```

### CPP

```cpp
class Solution {
public:
  int maxDistance(vector<int> &position, int m) {
    sort(position.begin(), position.end());
    int left = 1, right = position[position.size() - 1];
    while (left < right) {
      int mid = (left + right + 1) >> 1;
      if (check(position, mid, m))
        left = mid;
      else
        right = mid - 1;
    }
    return left;
  }
  bool check(vector<int> &position, int f, int m) {
    int prev = position[0];
    int cnt = 1;
    for (int i = 1; i < position.size(); ++i) {
      int curr = position[i];
      if (curr - prev >= f) {
        prev = curr;
        ++cnt;
      }
    }
    return cnt >= m;
  }
};

```

### Python

```python
class Solution:
    def maxDistance(self, position: List[int], m: int) -> int: def check(f): prev = position[0] cnt = 1 for curr in position[1:]: if curr - prev >= f: prev = curr cnt += 1 return cnt >= m position . sort() left, right = 1, position[- 1] while left < right: mid = (left + right + 1) >> 1 if check(mid): left = mid else: right = mid - 1 return left

```