Show problems as
Classic problem #1552MediumArrayBinary SearchSorting

Magnetic Force Between Two Balls

Real-world version: Widest Clearance for Channel Buoys
Tracked in this browser only
Read Magnetic Force Between Two Balls on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A survey team works along one bank of a straight drainage channel where mooring posts have been driven into the ground. posts[i] is the distance in metres of one post from the channel mouth. The distances are all different and they arrive in no particular order.

The team has buoys instrument buoys to tie up. Each buoy must go on a post, and no post can take more than one buoy. Every buoy must be used. For an arrangement, the distance between two buoys is the absolute difference of their posts' distances, and the arrangement's clearance is the smallest distance between any two of the moored buoys.

Return the largest clearance that any arrangement can achieve.

Examples

Example 1

Input
posts = [9, 2, 14, 5], buoys = 3
Output
5

The reported figure is met by mooring on the posts at 2, 9 and 14, which leaves neighbouring buoys 7 and 5 metres apart.

Example 2

Input
posts = [1, 2, 3, 4, 20], buoys = 3
Output
3

The reported figure is met by mooring at 1, 4 and 20, which leaves gaps of 3 and 16 metres.

Example 3

Input
posts = [7, 12], buoys = 2
Output
5

Only two posts exist and both must take a buoy, so the clearance is the span between them.

Example 4

Input
posts = [31, 4, 17, 25, 12, 8], buoys = 6
Output
4

Every post takes a buoy, so the clearance is the tightest gap along the whole line, which measures 4 metres.

Constraints

  • n == posts.length
  • 2 <= n <= 10^5
  • 1 <= posts[i] <= 10^9
  • All values in posts are distinct.
  • 2 <= buoys <= posts.length

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def widest_spacing(posts: list[int], buoys: int) -> int:
Java
public int widestSpacing(int[] posts, int buoys)

More on the same topics