Maximize the Distance Between Points on a Square

Start by recognizing that the problem requires maximizing the minimum Manhattan distance among selected points on a square boundary. Use binary search over possible distances, and for each candidate, verify feasibility with a greedy approach. This ensures the largest achievable minimum distance is found efficiently while handling constraints on points placement.

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). You are also given a 2D array points, where each points[i] = [xi, yi] represents a unique point lying on the boundary of the square.

Your task is to choose k points from the given points such that the minimum Manhattan distance between any two chosen points is maximized. Return this maximum possible distance as an integer.

Examples

Example 1

Input: side = 2, points = [[0,2],[2,0],[2,2],[0,0]], k = 4

Output: 2

Select all four points.

Example 2

Input: side = 2, points = [[0,0],[1,2],[2,0],[2,2],[2,1]], k = 4

Output: 1

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

Select the points (0, 0) , (0, 1) , (0, 2) , (1, 2) , and (2, 2) .

Constraints

• 1 <= side <= 109
• 4 <= 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.

• points[i] lies on the boundary of the square.
• All points[i] are unique.
• 4 <= k <= min(25, points.length)

Solution Approach

Binary Search on Distance

Perform a binary search over the range of possible minimum distances. For each distance mid, check if it is possible to select k points such that all pairs are at least mid apart. This uses the problem's primary pattern of binary search over valid answer space.

Greedy Feasibility Check

For each candidate distance from binary search, iterate through points in order along the square's perimeter and greedily select points that maintain the minimum distance. Stop when k points are selected or if it becomes impossible. This step ensures efficiency in validating each candidate distance.

Edge Mapping and Sorting

Map points onto a linear representation of the square boundary to simplify distance calculations. Sort the points along this 1D perimeter before applying greedy selection. This avoids corner-case errors and aligns with the Manhattan distance constraints specific to this square layout.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n log L), where n is the number of points and L is the maximum possible distance (side of the square). Each binary search iteration performs a linear pass over points for the greedy check. Space complexity is O(n) for storing sorted points and mapping them to a linear boundary.

What Interviewers Usually Probe

• Can you apply binary search to the maximum distance instead of checking all pairs?
• Consider a linear mapping of the square boundary to simplify distance calculations.
• Think about greedy selection once candidate distances are chosen by binary search.

Common Pitfalls or Variants

Common pitfalls

• Failing to map 2D points to a linear perimeter, leading to incorrect distance calculations across corners.
• Assuming Euclidean distance instead of Manhattan distance, which changes feasibility checks.
• Not sorting points along the boundary before greedy selection, causing missed valid configurations.

Follow-up variants

• Maximize distance using Euclidean distance instead of Manhattan distance.
• Select points on a rectangle or polygon boundary instead of a square.
• Increase k beyond the standard limit, testing scalability of binary search and greedy strategy.

FAQ

What is the best approach to maximize the distance between points on a square?

Use binary search over possible minimum distances combined with a greedy selection along the square perimeter.

Why is greedy selection necessary in this problem?

Greedy selection ensures that each chosen point maintains the required minimum distance, validating candidate distances efficiently.

Do we use Manhattan or Euclidean distance here?

Manhattan distance is used because the points lie on the square boundary and distances are measured along grid-aligned edges.

How should points be ordered before selection?

Map the square boundary to a linear sequence and sort points along it to simplify distance checks.

Can binary search handle large side lengths?

Yes, binary search efficiently narrows down the maximum distance even for large squares, avoiding brute-force pair comparisons.