Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Map the boundary to a circle of circumference 4 * side. With at least four selected points, some consecutive perimeter gap is at most side, so the optimum cannot exceed side. For thresholds in that range, enforcing all circular gaps is equivalent to the Manhattan-distance condition: same-side or adjacent-side short distances follow the boundary, while opposite sides are already at least side apart.

Approach

Convert each point to its clockwise perimeter coordinate starting at (0, 0), then sort. Binary-search the required minimum distance from one through side.

For a candidate distance, try each possible first point. Repeatedly binary-search the earliest later coordinate at least that distance from the last chosen point. Also require enough wraparound distance from the new point back to the first. Choosing the earliest feasible successor leaves the most space for all later choices and for closing the circle.

Accept when k points are chosen. If no next point exists, later starting positions cannot fit more successors, so the check can fail immediately. Feasibility is monotone as the distance decreases, making binary search return the largest feasible value.

class Solution:
    def maxDistance(self, side: int, points: List[List[int]], k: int) -> int:
        n = len(points)
        points2 = []
        # distances from 0,0

        for x, y in points:
            if y == 0:
                points2.append(x)
            elif x == 0:
                points2.append(side * 3 + (side - y))
            elif y == side:
                points2.append(side * 2 + (side - x))
            elif x == side:
                points2.append(side + y)

        points2.sort()

        def check(mn):
            for i in range(n):
                count = 1
                curr = i
                while count < k:
                    jump = bisect.bisect_left(points2, points2[curr] + mn)
                    if jump >= len(points2):
                        return False
                    if points2[i] + 4 * side - points2[jump] < mn:
                        break
                    count += 1
                    curr = jump
                if count == k:
                    return True
            return False

        l = 1
        h = side

        while l < h:
            mid = l + (h - l + 1) // 2
            if check(mid):
                l = mid
            else:
                h = mid - 1

        return l

Complexity analysis

Let n = points.length, S = side, and k be the number selected. Time: O(n log n + n * k * log n * log S). Auxiliary space: O(n).