You are given an integer side, representing the edge length of a square with corners at (0, 0), (0, side), (side, 0), and (side, side) on a Cartesian plane.
You are also given a positive integer k and a 2D integer array points, where points[i] = [xi, yi] represents the coordinate of a point lying on the boundary of the square.
You need to select k elements among points such that the minimum Manhattan distance between any two points is maximized.
Return the maximum possible minimum Manhattan distance between the selected k points.
The Manhattan Distance between two cells (xi, yi) and (xj, yj) is |xi - xj| + |yi - yj|.
Example 1:
Input: side = 2, points = [[0,2],[2,0],[2,2],[0,0]], k = 4
Output: 2
Explanation:
Select all four points.
Example 2:
Input: side = 2, points = [[0,0],[1,2],[2,0],[2,2],[2,1]], k = 4
Output: 1
Explanation:
Select the points (0, 0), (2, 0), (2, 2), and (2, 1).
Example 3:
Input: side = 2, points = [[0,0],[0,1],[0,2],[1,2],[2,0],[2,2],[2,1]], k = 5
Output: 1
Explanation:
Select the points (0, 0), (0, 1), (0, 2), (1, 2), and (2, 2).
Constraints:
1 <= side <= 1094 <= points.length <= min(4 * side, 15 * 103)points[i] == [xi, yi]points[i] lies on the boundary of the square.points[i] are unique.4 <= k <= min(25, points.length)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.
Since the problem asks to maximize the minimum distance, we can use binary search on the answer to find the optimal solution.
First, to simplify the logic, we map the 2D coordinates (x, y) on the square's boundary to a 1D axis [0, 4 times side). The mapping rules are as follows:
x = 0, the mapped value is y;y = side, the mapped value is side + x;x = side, the mapped value is 3 times side - y;4 times side - x.After mapping, sort all the points to obtain the array nums. Since the points are selected on the perimeter of the square, this is essentially a circular (ring) problem.
During the binary search, for a given minimum distance lo, we use a check function to verify its feasibility:
nums as the starting point start.end = start + 4 times side - lo, ensuring that the wrap-around distance from the last selected point back to start is at least lo.k-1 jumps, each time using binary search to quickly locate the next point that is at least lo away from the current position.k points within the end limit, then the distance lo is feasible.The time complexity is O(n log (side) cdot n log n) and the space complexity is O(n), where n is the length of the points array.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Combination | O(C(n,k) * k) | O(k) | Small inputs where n and k are tiny or for validating logic |
| Perimeter Mapping + Sorting | O(n log n) | O(n) | Preprocessing step to convert 2D boundary points into ordered perimeter positions |
| Binary Search with Greedy Placement | O(n log P) | O(n) | Optimal solution when maximizing minimum distance on circular perimeter |
Maximize the Distance Between Points on a Square | Super Detailed Intuition | Leetcode 3464 | MIK • codestorywithMIK • 5,681 views views
Watch 9 more video solutions →Practice Maximize the Distance Between Points on a Square with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor