Maximize the Distance Between Points on a Square - Solution & Explanation

Problem Overview: You are given points on the boundary of a square and must choose k of them such that the minimum distance between any pair is maximized. Since all points lie on the perimeter, the key idea is to convert the 2D boundary into a 1D circular distance problem and then search for the largest feasible spacing.

Approach 1: Brute Force Combination Check (Exponential Time, O(C(n,k) * k))

Generate every combination of k points and compute the minimum pairwise distance within that subset. Track the maximum of these minimum distances. Distance is measured along the square boundary, so each pair requires perimeter distance computation. This approach is straightforward but infeasible for large n because combinations grow exponentially. Space complexity is O(k) for recursion or combination storage.

Approach 2: Perimeter Mapping + Binary Search (O(n log n + n log P))

Each boundary point can be mapped to a single scalar position along the square’s perimeter. For a square of side L, compute the distance from a fixed corner while walking clockwise. After mapping, sort these positions using sorting. The problem becomes selecting k positions on a circular line so that the minimum gap between consecutive chosen points is maximized.

Use binary search on the answer. For a candidate minimum distance d, greedily attempt to pick points while maintaining at least d separation along the perimeter. Because the perimeter forms a cycle, duplicate the array (append positions + perimeter length) to simulate wraparound and check feasibility from each starting point. This greedy feasibility check runs in O(n). Binary search over the distance range (0 to perimeter) gives total time O(n log P) with O(n) extra space.

The geometry component is only used to convert coordinates into perimeter distance; after that the algorithm behaves like a classic spacing optimization problem. See related techniques in arrays and geometry problems.

Recommended for interviews: The perimeter mapping plus binary search approach. Interviewers expect you to recognize the "maximize the minimum distance" pattern and apply binary search with a greedy feasibility check. Mentioning the brute force approach first shows understanding of the objective, but the binary search optimization demonstrates strong algorithmic reasoning.