Maximize the Distance Between Points on a Square

Problem summary

We are given points on the boundary of a square with side length side.

We need to choose exactly k of those points so that the minimum Manhattan distance between any two chosen points is as large as possible.

This is a classic maximize the minimum problem, so the outer structure is binary search on the answer.

Key observation

Because k >= 4, the answer can never be larger than side.

• If k > 4, at least two selected points must share an edge, and two points on the same edge are at distance at most side.
• If k = 4, the best possible case is selecting the four corners, whose minimum distance is exactly side.

So we only need to binary search from 1 to side.

Unfold the square

The tricky part is checking whether a candidate distance is possible.

Instead of reasoning directly in 2D, unfold the boundary of the square into a one-dimensional circular line of length 4 * side.

Use this clockwise mapping:

• Left edge x = 0: value = y
• Top edge y = side: value = side + x
• Right edge x = side: value = 3 * side - y
• Bottom edge y = 0: value = 4 * side - x

After this conversion, points on the boundary become numbers on a circular perimeter.

For distances up to side, this preserves the important minimum-distance behavior:

• same-edge and adjacent-edge distances match their Manhattan distances
• opposite-edge pairs are already at least side, so they cannot reduce an answer smaller than or equal to side

Feasibility check

For a candidate distance limit, ask:

Can we select k positions on this circular line such that every adjacent selected pair is at least limit apart, including the wrap-around pair?

Pick a start position, then greedily choose the next position that is at least limit away. Binary search with lower_bound finds that next position.

The circular condition is handled by limiting the last chosen point:

If the first selected position is start, the last selected position must be at most:

start + 4 * side - limit

That ensures the wrap-around distance from the last selected point back to start is also at least limit.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int maxDistance(int side, int[][] points, int k) {
        List<Long> positions = new ArrayList<>();

        for (int[] point : points) {
            int x = point[0];
            int y = point[1];

            if (x == 0) {
                positions.add((long) y);
            } else if (y == side) {
                positions.add((long) side + x);
            } else if (x == side) {
                positions.add(3L * side - y);
            } else {
                positions.add(4L * side - x);
            }
        }

        Collections.sort(positions);

        int answer = 0;
        long left = 1;
        long right = side;

        while (left <= right) {
            long mid = left + (right - left) / 2;

            if (canPick(positions, side, k, mid)) {
                answer = (int) mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return answer;
    }

    private boolean canPick(List<Long> positions, int side, int k, long limit) {
        long perimeter = 4L * side;

        for (long start : positions) {
            long lastAllowed = start + perimeter - limit;
            long current = start;
            boolean possible = true;

            for (int picked = 1; picked < k; picked++) {
                int next = lowerBound(positions, current + limit);

                if (next == positions.size() || positions.get(next) > lastAllowed) {
                    possible = false;
                    break;
                }

                current = positions.get(next);
            }

            if (possible) {
                return true;
            }
        }

        return false;
    }

    private int lowerBound(List<Long> positions, long target) {
        int left = 0;
        int right = positions.size();

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (positions.get(mid) < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return left;
    }
}

Complexity

Let n = points.length.

• Time: O(n log n + n * k * log n * log side)
• Space: O(n)

Since k <= 25, this is fast enough for n <= 15000.

Interview note

The important move is not the binary search itself. It is converting the square boundary into a circular one-dimensional array, then realizing the check becomes a greedy spacing problem with one wrap-around constraint.