LeetCode 1552: Magnetic Force Between Two Balls (Binary Search on Answer + Greedy Placement)
LeetCode 1552Binary SearchGreedyToday we solve LeetCode 1552 - Magnetic Force Between Two Balls.
Source: https://leetcode.com/problems/magnetic-force-between-two-balls/
English
Problem Summary
Given basket positions and m balls, place all balls so that the minimum distance between any two placed balls is as large as possible. Return that maximum possible minimum distance.
Key Insight
If we guess a minimum distance d, we can greedily place balls from left to right in sorted positions and check whether placing m balls is feasible. This feasibility is monotonic: if distance d is feasible, any smaller distance is also feasible.
Algorithm
- Sort positions.
- Binary search answer d in [1, maxPos - minPos].
- Feasibility check: place first ball at first basket; each next ball goes to the earliest basket at least d away from the last placed one.
- If we can place at least m balls, d is feasible and we try larger; otherwise try smaller.
Complexity Analysis
Sorting: O(n log n).
Each check: O(n), and binary search runs O(log R), where R = maxPos - minPos.
Total: O(n log n + n log R).
Extra space: O(1) (ignoring sort internals).
Common Pitfalls
- Forgetting to sort first.
- Using wrong binary-search midpoint update and getting infinite loop.
- Starting lower bound at 0 (works but less clean); distance 1 is enough for distinct positions.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
import java.util.Arrays;
class Solution {
public int maxDistance(int[] position, int m) {
Arrays.sort(position);
int lo = 1, hi = position[position.length - 1] - position[0];
int ans = 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (canPlace(position, m, mid)) {
ans = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return ans;
}
private boolean canPlace(int[] pos, int m, int dist) {
int count = 1;
int last = pos[0];
for (int i = 1; i < pos.length; i++) {
if (pos[i] - last >= dist) {
count++;
last = pos[i];
if (count >= m) return true;
}
}
return count >= m;
}
}import "sort"
func maxDistance(position []int, m int) int {
sort.Ints(position)
lo, hi := 1, position[len(position)-1]-position[0]
ans := 1
canPlace := func(dist int) bool {
count := 1
last := position[0]
for i := 1; i < len(position); i++ {
if position[i]-last >= dist {
count++
last = position[i]
if count >= m {
return true
}
}
}
return count >= m
}
for lo <= hi {
mid := lo + (hi-lo)/2
if canPlace(mid) {
ans = mid
lo = mid + 1
} else {
hi = mid - 1
}
}
return ans
}#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxDistance(vector<int>& position, int m) {
sort(position.begin(), position.end());
int lo = 1, hi = position.back() - position.front();
int ans = 1;
auto canPlace = [&](int dist) {
int count = 1;
int last = position[0];
for (int i = 1; i < (int)position.size(); i++) {
if (position[i] - last >= dist) {
count++;
last = position[i];
if (count >= m) return true;
}
}
return count >= m;
};
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (canPlace(mid)) {
ans = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return ans;
}
};class Solution:
def maxDistance(self, position: list[int], m: int) -> int:
position.sort()
lo, hi = 1, position[-1] - position[0]
ans = 1
def can_place(dist: int) -> bool:
count = 1
last = position[0]
for x in position[1:]:
if x - last >= dist:
count += 1
last = x
if count >= m:
return True
return count >= m
while lo <= hi:
mid = (lo + hi) // 2
if can_place(mid):
ans = mid
lo = mid + 1
else:
hi = mid - 1
return ansvar maxDistance = function(position, m) {
position.sort((a, b) => a - b);
let lo = 1;
let hi = position[position.length - 1] - position[0];
let ans = 1;
const canPlace = (dist) => {
let count = 1;
let last = position[0];
for (let i = 1; i < position.length; i++) {
if (position[i] - last >= dist) {
count++;
last = position[i];
if (count >= m) return true;
}
}
return count >= m;
};
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
if (canPlace(mid)) {
ans = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return ans;
};中文
题目概述
给定若干篮子位置 position 和球数 m，要把 m 个球放进这些篮子里，使任意两球之间的最小距离尽可能大。返回这个最小距离的最大值。
核心思路
对“最小距离”做答案二分。假设距离为 d，将位置排序后从左到右贪心放球：每次放到第一个与上一个球相距至少 d 的篮子。若能放满 m 个球，说明 d 可行。可行性具有单调性，可以二分。
算法步骤
- 先排序。
- 在区间 [1, max-min] 上二分最小距离。
- 编写 check(d) 贪心校验是否能放下 m 个球。
- 可行就扩大距离，不可行就缩小距离。
复杂度分析
排序复杂度 O(n log n)。
每次校验 O(n)，二分次数 O(log R)（R=max-min）。
总复杂度 O(n log n + n log R)。
额外空间 O(1)（不计排序栈空间）。
常见陷阱
- 没有先排序，贪心校验失效。
- 二分边界更新写反导致死循环。
- 可行后忘记记录答案。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
import java.util.Arrays;
class Solution {
public int maxDistance(int[] position, int m) {
Arrays.sort(position);
int lo = 1, hi = position[position.length - 1] - position[0];
int ans = 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (canPlace(position, m, mid)) {
ans = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return ans;
}
private boolean canPlace(int[] pos, int m, int dist) {
int count = 1;
int last = pos[0];
for (int i = 1; i < pos.length; i++) {
if (pos[i] - last >= dist) {
count++;
last = pos[i];
if (count >= m) return true;
}
}
return count >= m;
}
}import "sort"
func maxDistance(position []int, m int) int {
sort.Ints(position)
lo, hi := 1, position[len(position)-1]-position[0]
ans := 1
canPlace := func(dist int) bool {
count := 1
last := position[0]
for i := 1; i < len(position); i++ {
if position[i]-last >= dist {
count++
last = position[i]
if count >= m {
return true
}
}
}
return count >= m
}
for lo <= hi {
mid := lo + (hi-lo)/2
if canPlace(mid) {
ans = mid
lo = mid + 1
} else {
hi = mid - 1
}
}
return ans
}#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxDistance(vector<int>& position, int m) {
sort(position.begin(), position.end());
int lo = 1, hi = position.back() - position.front();
int ans = 1;
auto canPlace = [&](int dist) {
int count = 1;
int last = position[0];
for (int i = 1; i < (int)position.size(); i++) {
if (position[i] - last >= dist) {
count++;
last = position[i];
if (count >= m) return true;
}
}
return count >= m;
};
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (canPlace(mid)) {
ans = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return ans;
}
};class Solution:
def maxDistance(self, position: list[int], m: int) -> int:
position.sort()
lo, hi = 1, position[-1] - position[0]
ans = 1
def can_place(dist: int) -> bool:
count = 1
last = position[0]
for x in position[1:]:
if x - last >= dist:
count += 1
last = x
if count >= m:
return True
return count >= m
while lo <= hi:
mid = (lo + hi) // 2
if can_place(mid):
ans = mid
lo = mid + 1
else:
hi = mid - 1
return ansvar maxDistance = function(position, m) {
position.sort((a, b) => a - b);
let lo = 1;
let hi = position[position.length - 1] - position[0];
let ans = 1;
const canPlace = (dist) => {
let count = 1;
let last = position[0];
for (let i = 1; i < position.length; i++) {
if (position[i] - last >= dist) {
count++;
last = position[i];
if (count >= m) return true;
}
}
return count >= m;
};
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
if (canPlace(mid)) {
ans = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return ans;
};
Comments