3464. Maximize the Distance Between Points on a Square

Array
Binary Search
Greedy

TIME

O(n k log n * log(perimeter/k))

SPACE

O(n)

Intuition

Key insight: For points on a square boundary, Manhattan distance equals the minimum of clockwise and counter-clockwise perimeter distances.

Map 2D boundary points to 1D perimeter positions
Binary search on the minimum distance
Greedy check: can we select k points with all consecutive gaps >= d?

Solution

Step 1: Map to Perimeter Positions

Traverse boundary clockwise from (0,0):

Bottom (y=0): position = x
Right (x=side): position = side + y
Top (y=side): position = 2*side + (side - x)
Left (x=0): position = 3*side + (side - y)

Step 2: Binary Search + Greedy Check

For a candidate minimum distance d:

Try each point as starting point
Greedily select next point with gap >= d
After selecting k points, verify wrap-around gap is also >= d

def canAchieve(d):
    for start in range(n):
        count = 1
        last_idx = start
        
        for _ in range(k - 1):
            # Binary search for next valid position
            target = extended[last_idx] + d
            next_idx = bisect_left(extended, target, last_idx + 1, start + n)
            
            if next_idx >= start + n:
                break
            count += 1
            last_idx = next_idx
        
        if count == k:
            wrap_dist = extended[start + n] - extended[last_idx]
            if wrap_dist >= d:
                return True
    return False

Complexity

Time: O(n × k × log n × log(perimeter/k))
Space: O(n)

Edge Cases

All points at corners
Points evenly distributed
k equals number of points

Code

from typing import List
from bisect import bisect_left


class Solution:
    def maxDistance(self, side: int, points: List[List[int]], k: int) -> int:
        """
        3464. Maximize the Distance Between Points on a Square
        Time: O(n * k * log n * log(perimeter/k))
        Space: O(n)
        """
        perimeter = 4 * side

        def to_perimeter_pos(x: int, y: int) -> int:
            if y == 0:
                return x
            elif x == side:
                return side + y
            elif y == side:
                return 2 * side + (side - x)
            else:
                return 3 * side + (side - y)

        positions = sorted(to_perimeter_pos(x, y) for x, y in points)
        n = len(positions)

        # Double the array for cyclic handling
        extended = positions + [p + perimeter for p in positions]

        def canAchieve(d: int) -> bool:
            for start in range(n):
                count = 1
                last_idx = start

                for _ in range(k - 1):
                    target = extended[last_idx] + d
                    next_idx = bisect_left(extended, target, last_idx + 1, start + n)

                    if next_idx >= start + n:
                        break

                    count += 1
                    last_idx = next_idx

                if count == k:
                    wrap_dist = extended[start + n] - extended[last_idx]
                    if wrap_dist >= d:
                        return True

            return False

        lo, hi = 1, perimeter // k
        ans = 1

        while lo <= hi:
            mid = (lo + hi) // 2
            if canAchieve(mid):
                ans = mid
                lo = mid + 1
            else:
                hi = mid - 1

        return ans

import java.util.*;

/**
 * 3464. Maximize the Distance Between Points on a Square
 * Time: O(n * k * log n * log(perimeter/k))
 * Space: O(n)
 */
class Solution {
    private long[] extended;
    private int n;
    private int k;

    public int maxDistance(int side, int[][] points, int k) {
        this.k = k;
        long perimeter = 4L * side;

        long[] positions = new long[points.length];
        for (int i = 0; i < points.length; i++) {
            positions[i] = toPerimeterPos(points[i][0], points[i][1], side);
        }
        Arrays.sort(positions);
        n = positions.length;

        // Double array for cyclic handling
        extended = new long[2 * n];
        for (int i = 0; i < n; i++) {
            extended[i] = positions[i];
            extended[i + n] = positions[i] + perimeter;
        }

        long lo = 1, hi = perimeter / k;
        long ans = 1;

        while (lo <= hi) {
            long mid = (lo + hi) / 2;
            if (canAchieve(mid)) {
                ans = mid;
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }

        return (int) ans;
    }

    private long toPerimeterPos(int x, int y, int side) {
        if (y == 0) {
            return x;
        } else if (x == side) {
            return (long) side + y;
        } else if (y == side) {
            return 2L * side + (side - x);
        } else {
            return 3L * side + (side - y);
        }
    }

    private boolean canAchieve(long d) {
        for (int start = 0; start < n; start++) {
            int count = 1;
            int lastIdx = start;

            for (int i = 0; i < k - 1; i++) {
                long target = extended[lastIdx] + d;
                int nextIdx = lowerBound(extended, target, lastIdx + 1, start + n);

                if (nextIdx >= start + n) {
                    break;
                }

                count++;
                lastIdx = nextIdx;
            }

            if (count == k) {
                long wrapDist = extended[start + n] - extended[lastIdx];
                if (wrapDist >= d) {
                    return true;
                }
            }
        }

        return false;
    }

    private int lowerBound(long[] arr, long target, int lo, int hi) {
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (arr[mid] >= target) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }
}