0918HardArrayMathBinary SearchGeometrySorting

Spreading Marks Round a Square Fence

Tracked in this browser only

Trains the technique from

LeetCode 3464Maximize the Distance Between Points on a Square

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 square fence has its corners at (0, 0), (side, 0), (side, side) and (0, side). Candidate posts are given as points, each [x, y] lying on the fence itself, and all of them are distinct.

Choose k of the posts. The spread of a choice is the smallest distance between any two posts chosen, measured as the difference in x plus the difference in y.

Return the largest spread any choice of k posts can have.

Examples

Example 1

Input: side = 12, points = [[0, 0], [12, 0], [12, 12], [0, 12], [6, 0], [12, 6]], k = 4
Output: 12

Taking the four corners leaves every neighbouring pair 12 apart, and no choice of four posts spreads them further.

Example 2

Input: side = 2, points = [[0, 0], [1, 0], [2, 0], [2, 1], [2, 2], [1, 2], [0, 2], [0, 1]], k = 8
Output: 1

Every post on the fence has to be taken, and the closest neighbouring pair sits one apart.

Example 3

Input: side = 1000000000, points = [[0, 0], [1000000000, 0], [1000000000, 1000000000], [0, 1000000000]], k = 4
Output: 1000000000

Only the four corners are on offer, so the spread is the side length itself.

Constraints

1 <= side <= 10^9
4 <= points.length <= 1000
points[i].length == 2
Every point lies on the fence
All the points are different
4 <= k <= points.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 max_distance(side: int, points: list[list[int]], k: int) -> int:

Java

public int maxDistance(int side, int[][] points, int k)

The intended approach

Time O(n^2 log(side)) for n posts, each candidate spread costing a pass per starting post.Space O(n) for the posts in fence order.

The spread only ever falls as more posts are demanded, and asking whether a given spread is reachable is easier than asking for the best one, so halve the range of candidate spreads from one up to twice the side, which is as far apart as two posts on the fence can be. To test a candidate, lay the posts out in the order they appear walking round the fence. Then a choice is a set of positions on a ring, and picking them greedily works: fix which post is taken first, walk forward taking the next post that is far enough from the one just taken, and check both that `k` posts were taken and that the last one is far enough from the first. Because the ring has no natural beginning, every post has to be tried as the first, which is what makes the test quadratic.

Pythonentry point: max_distance

def max_distance(side, points, k):
    def around(p):
        x, y = p
        if y == 0:
            return x
        if x == side:
            return side + y
        if y == side:
            return 3 * side - x
        return 4 * side - y

    order = sorted(points, key=around)
    n = len(order)

    def gap(a, b):
        return abs(order[a][0] - order[b][0]) + abs(order[a][1] - order[b][1])

    def reachable(want):
        for start in range(n):
            taken = 1
            last = start
            step = 1
            while step < n and taken < k:
                at = (start + step) % n
                if gap(last, at) >= want:
                    taken += 1
                    last = at
                step += 1
            if taken == k and gap(last, start) >= want:
                return True
        return False

    low = 1
    high = 2 * side
    best = 0
    while low <= high:
        mid = (low + high) // 2
        if reachable(mid):
            best = mid
            low = mid + 1
        else:
            high = mid - 1
    return best

The obvious version

Take every choice of `k` posts, work out the smallest distance between any two of them, and keep the largest such figure. Exponential in the post count, and it compares all pairs rather than relying on posts being ordered round the fence.

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_max_distance(side, points, k):
    import itertools
    best = 0
    n = len(points)
    for combo in itertools.combinations(range(n), k):
        closest = None
        for i in range(len(combo)):
            for j in range(i + 1, len(combo)):
                a = points[combo[i]]
                b = points[combo[j]]
                d = abs(a[0] - b[0]) + abs(a[1] - b[1])
                if closest is None or d < closest:
                    closest = d
        if closest is not None and closest > best:
            best = closest
    return best

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
3 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