Maximize the Distance Between Points on a Square - Video Solutions
Maximize the Distance Between Points on a Square | Super Detailed Intuition | Leetcode 3464 | MIK
Maximize the Distance Between Points on a Square - Video Solution
Watch 10 video solutions for Maximize the Distance Between Points on a Square, a hard level problem involving Array, Math, Binary Search. This walkthrough by codestorywithMIK has 5,681 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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]- The input is generated such that:
points[i]lies on the boundary of the square.- All
points[i]are unique.
4 <= k <= min(25, points.length)
Approach Overview
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.
Complexity Analysis
| 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 |