
Intuition
The problem requires us to place m
balls into n
baskets such that the minimum magnetic force (|x - y|) between any two balls is maximized. This can be approached by maximizing the minimum distance between the balls placed in the baskets. To achieve this, we can use a binary search strategy on the potential values of this minimum distance.
Approach
- Sort the Positions: Begin by sorting the
position
array. This helps in simplifying the problem since it allows us to perform binary search and check possible distances sequentially. - Binary Search: Use binary search to find the maximum minimum distance:
- Set the initial range for binary search:
lo
to0
andhi
to the difference between the maximum and minimum positions in the array. - For each midpoint in the binary search (mid
), check if it is possible to place allm
balls such that the minimum distance between any two balls is at leastmid
. - Feasibility Check: To determine if a given distance
mid
is feasible: - Place the first ball in the first basket. - For each subsequent basket, place the next ball only if the distance from the last placed ball is at leastmid
. - If we can place allm
balls this way, the distancemid
is feasible. - Adjust Binary Search Range: Based on the feasibility check:
- If the distance
mid
is feasible, move the lower bound up (lo = mid + 1
) to try for a larger minimum distance. - If the distancemid
is not feasible, move the upper bound down (hi = mid
). - Result: The maximum value of the feasible minimum distance found through binary search will be the answer.
Complexity
- Time complexity: O(n log(maxDistance))
- Sorting the
position
array takes O(n log n). - The binary search runs in O(log(maxDistance)) wheremaxDistance
is the difference between the maximum and minimum positions. - Each feasibility check takes O(n), iterating through the baskets. - Overall, the time complexity is O(n log n + n log(maxDistance)) which simplifies to O(n log(maxDistance)). - Space complexity: O(1) - The algorithm uses a constant amount of extra space apart from the input array.
Code
C++
class Solution {
public:
int maxDistance(vector& position, int m) {
sort(position.begin(), position.end());
return bisectLeft(position, m - 1);
}
private:
int bisectLeft(const vector& arr, int m) {
int lo = 0;
int hi = arr.back() - arr.front();
while (lo < hi) {
int mid = (lo + hi) >> 1;
if (isPossible(arr, mid, m)) {
lo = mid + 1;
} else {
hi = mid;
}
}
return isPossible(arr, lo, m) ? lo : lo - 1;
}
bool isPossible(const vector& arr, int mid, int m) {
int prev = arr[0];
for (int x : arr) {
if (x - prev >= mid) {
if (m-- == 1)
return true;
prev = x;
}
}
return false;
}
};
Python
class Solution:
def maxDistance(self, position: List[int], m: int) -> int:
position.sort()
return self.bisectLeft(position, m - 1)
def bisectLeft(self, arr: List[int], m: int) -> int:
lo, hi = 0, arr[-1] - arr[0]
while lo < hi:
mid = (lo + hi) // 2
if self.isPossible(arr, mid, m):
lo = mid + 1
else:
hi = mid
return lo if self.isPossible(arr, lo, m) else lo - 1
def isPossible(self, arr: List[int], mid: int, m: int) -> bool:
prev = arr[0]
for x in arr:
if x - prev >= mid:
m -= 1
if m == 0:
return True
prev = x
return False
Java
class Solution {
public int maxDistance(int[] position, int m) {
Arrays.sort(position);
return bisectLeft(position, m - 1);
}
private int bisectLeft(int[] arr, int m) {
int lo = 0;
int hi = arr[arr.length - 1] - arr[0];
while (lo < hi) {
int mid = (lo + hi) >> 1;
if (isPossible(arr, mid, m)) {
lo = mid + 1;
} else {
hi = mid;
}
}
return isPossible(arr, lo, m) ? lo : lo - 1;
}
private boolean isPossible(int[] arr, int mid, int m) {
int prev = arr[0];
for (int x : arr) {
if (x - prev >= mid) {
if (m-- == 1) {
return true;
}
prev = x;
}
}
return false;
}
}
JavaScript
/**
* @param {number[]} position
* @param {number} m
* @return {number}
*/
var maxDistance = function (position, m) {
position.sort((a, b) => a - b);
return bisectLeft(position, m - 1);
};
/**
* @param {number[]} arr
* @param {number} m
* @returns {number} Equal or less than equal value
*/
var bisectLeft = function (arr, m) {
var lo = 0;
var hi = arr[arr.length - 1] - arr[0];
while (lo < hi) {
var mid = (lo + hi) >> 1;
isPossible(arr, mid, m) ? (lo = mid + 1) : (hi = mid);
}
return isPossible(arr, lo, m) ? lo : lo - 1;
};
/**
* @param {number[]} arr
* @param {number} mid
* @param {number} m
* @returns {number}
*/
var isPossible = function (arr, mid, m) {
var prev = arr[0];
for (var x of arr) {
if (x - prev >= mid) {
if (m-- === 1) return true;
prev = x;
}
}
return false;
};
Go
func maxDistance(position []int, m int) int {
sort.Ints(position)
return bisectLeft(position, m-1)
}
func bisectLeft(arr []int, m int) int {
lo := 0
hi := arr[len(arr)-1] - arr[0]
for lo < hi {
mid := (lo + hi) >> 1
if isPossible(arr, mid, m) {
lo = mid + 1
} else {
hi = mid
}
}
if isPossible(arr, lo, m) {
return lo
}
return lo - 1
}
func isPossible(arr []int, mid, m int) bool {
prev := arr[0]
for _, x := range arr {
if x-prev >= mid {
if m--; m == 0 {
return true
}
prev = x
}
}
return false
}
C#
public class Solution {
public int MaxDistance(int[] position, int m) {
Array.Sort(position);
return BisectLeft(position, m - 1);
}
private int BisectLeft(int[] arr, int m) {
int lo = 0;
int hi = arr[arr.Length - 1] - arr[0];
while (lo < hi) {
int mid = (lo + hi) >> 1;
if (IsPossible(arr, mid, m)) {
lo = mid + 1;
} else {
hi = mid;
}
}
return IsPossible(arr, lo, m) ? lo : lo - 1;
}
private bool IsPossible(int[] arr, int mid, int m) {
int prev = arr[0];
foreach (int x in arr) {
if (x - prev >= mid) {
if (m-- == 1) {
return true;
}
prev = x;
}
}
return false;
}
}
Conclusion
By leveraging binary search on the minimum possible distance between balls and employing a greedy approach to check the feasibility of placing balls at a given distance, we can efficiently determine the maximum possible minimum magnetic force between any two balls in the baskets. Sorting the basket positions initially simplifies the problem, allowing us to focus on the core challenge of distance maximization. This method ensures a time complexity of O(n log(maxDistance)) and a space complexity of O(1), making it a robust solution for the problem.