Magnetic Force Packages

Place K magnetic balls to maximize the minimum distance between them.

binary-search greedy array

You are distributing k identical magnetic balls into baskets located at integer positions on a number line. Each basket can hold at most one ball. To avoid attraction between the balls, you want to maximize the minimum distance between any two balls.

Implement the function `max_distance(positions, k)` that takes:
- `positions`: a list of distinct integer basket positions (not necessarily sorted).
- `k`: an integer, the number of balls to place.

Return the largest possible minimum distance between any two balls. The function should handle k between 2 and len(positions) inclusive.

Constraints

2 <= len(positions) <= 10^5
2 <= k <= len(positions)
0 <= positions[i] <= 10^9
All positions are distinct. You may assume the input is valid.
Expected time complexity: O(n log M) where n = len(positions) and M = max(positions) - min(positions).

Example

>>> max_distance([1, 2, 3, 4, 7], 3)
3
>>> max_distance([5, 4, 3, 2, 1, 1000000000], 2)
999999999
>>> max_distance([10, 2, 8], 2)
8

30 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Sort positions first; the answer is between 1 and max_pos - min_pos.

Use binary search on the answer and check if k balls can be placed with that minimum distance.

Greedily place a ball whenever the distance from the last placed ball is at least the candidate distance.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.