0439MediumArrayBinary SearchSorting

Widest Clearance for Channel Buoys

Tracked in this browser only

Trains the technique from

LeetCode 1552Magnetic Force Between Two Balls

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def widest_spacing(posts: list[int], buoys: int) -> int:

Java

public int widestSpacing(int[] posts, int buoys)

The intended approach

Time O(n log n + n log(max - min)): the sort dominates for small spans, and each of the O(log(max - min)) candidate clearances costs one linear sweep.Space O(n) for the sorted copy of the distances.

Order the distances, then search over the answer itself: a clearance of g is achievable exactly when a left-to-right sweep that moors a buoy the moment it is g or more clear of the last moored one can place all of them, and achievability only ever falls as g grows. Each sweep is linear, so a bisection over the range of candidate clearances settles the largest workable value.

Pythonentry point: widest_spacing

def widest_spacing(posts, buoys):
    # Clearance is monotone: if every pair can be kept at least g apart then it
    # can also be kept at least g-1 apart, so the achievable clearances form a
    # prefix of the integers and the largest one can be searched for. Testing a
    # candidate g only needs a left-to-right sweep of the sorted distances that
    # moors a buoy as soon as it is g clear of the last one moored.
    # O(n log n + n log(max - min)) time, O(n) space for the sorted copy.
    line = sorted(posts)

    def reaches(gap):
        moored = 1
        last = line[0]
        for spot in line:
            if spot - last >= gap:
                moored += 1
                last = spot
                if moored >= buoys:
                    return True
        return moored >= buoys

    low = 1
    high = line[-1] - line[0]
    best = 0
    while low <= high:
        mid = (low + high) // 2
        if reaches(mid):
            best = mid
            low = mid + 1
        else:
            high = mid - 1
    return best

The obvious version

Enumerate every choice of that many posts, take the tightest neighbouring gap within each choice, and keep the largest such gap seen.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_widest_spacing(posts, buoys):
    from itertools import combinations
    best = 0
    for choice in combinations(sorted(posts), buoys):
        tight = min(choice[i + 1] - choice[i] for i in range(len(choice) - 1))
        if tight > best:
            best = tight
    return best

How this problem was checked

Reference solution executed against 13 test cases — 13 passed
4 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in