Magnetic Force Between Two Balls
MediumArrayBinary SearchSorting
Solution
export function maxDistance(position: number[], m: number): number {
const n = position.length;
position.sort((a, b) => a - b);
function countBasket(distance: number) {
let result = 1;
let curr = position[0];
for (let i = 1; i < n; i++) {
if (distance <= position[i] - curr) {
result += 1;
curr = position[i];
}
}
return result;
}
let [left, right] = [0, position[n - 1] - position[0]];
while (left < right) {
const mid = right - Math.floor((right - left) / 2);
if (m <= countBasket(mid)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
Complexity
- Time:
O(N * log(N))
- Space:
O(1)