Maximize the Distance Between Points on a Square solution and explanation
Google
9 more videos on this problem
Maximize the Distance Between Points on a Square | Super Detailed Intuition | Leetcode 3464 | MIKcodestorywithMIK · 1:16:30 · 5K views
Maximize the distance between points on a square | HINDI | Leetcode 3464Aman Anand · 40:08 · 2K views
Maximize the Distance Between Points on a Square | LeetCode 3464 - Pythonimpoldev · 23:56 · 1K views
3464. Maximize the Distance Between Points on a Square | Leetcode Daily - PythonLeetcode Daily · 6:04 · 1K views
3464. Maximize the Distance Between Points on a Square (Leetcode Hard)Programming Live with Larry · 1:05:05 · 994 views
Maximize the Distance Between Points on a Square | Leetcode 3464 | Java | HindiKernel Queen 👑 · 19:54 · 555 views
Maximize the Distance Between Points on a Square | Leetcode - 3464Shivam Gupta · 25:41 · 554 views
Maximize the Distance Between Points on a Square | LeetCode 3464 🔥 | Binary Search + Greedy Explain Study Placement · 41:13 · 451 views
Daily Leetcode #2216: Apr 25, 2026 - 3464. Maximize the Distance Between Points on a SquareProgramming Live with Larry · 37:45 · 408 views
3464 Maximize the Distance Between Points on a SquareDaily LeetCode · 5:31 · 335 views
The problem
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.
Solution
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:
- If
x = 0, the mapped value isy; - If
y = side, the mapped value isside + x; - If
x = side, the mapped value is3 times side - y; - Otherwise, the mapped value is
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:
- Iterate through each point in
numsas the starting pointstart. - The endpoint for selecting points is
end = start + 4 times side - lo, ensuring that the wrap-around distance from the last selected point back tostartis at leastlo. - Then, greedily perform
k-1jumps, each time using binary search to quickly locate the next point that is at leastloaway from the current position. - If it is possible to select
kpoints within theendlimit, then the distancelois 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.
class Solution:
def maxDistance(self, side: int, points: List[List[int]], k: int) -> int:
nums = []
for x, y in points:
if x == 0:
nums.append(y)
elif y == side:
nums.append(side + x)
elif x == side:
nums.append(side * 3 - y)
else:
nums.append(side * 4 - x)
nums.sort()
def check(lo: int) -> bool:
for start in nums:
end = start + side * 4 - lo
cur = start
ok = True
for _ in range(k - 1):
j = bisect_left(nums, cur + lo)
if j == len(nums) or nums[j] > end:
ok = False
break
cur = nums[j]
if ok:
return True
return False
l, r = 1, side
while l < r:
mid = (l + r + 1) >> 1
if check(mid):
l = mid
else:
r = mid - 1
return lclass Solution {
private int side;
private long[] nums;
private int k;
public int maxDistance(int side, int[][] points, int k) {
this.side = side;
this.k = k;
int n = points.length;
this.nums = new long[n];
for (int i = 0; i < n; i++) {
int x = points[i][0];
int y = points[i][1];
if (x == 0) {
nums[i] = (long) y;
} else if (y == side) {
nums[i] = (long) side + x;
} else if (x == side) {
nums[i] = (long) side * 3 - y;
} else {
nums[i] = (long) side * 4 - x;
}
}
Arrays.sort(nums);
int l = 1, r = side;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (check(mid)) {
l = mid;
} else {
r = mid - 1;
}
}
return l;
}
private boolean check(int lo) {
long total = (long) side * 4;
for (int i = 0; i < nums.length; i++) {
long start = nums[i];
long end = start + total - lo;
long cur = start;
boolean ok = true;
for (int j = 0; j < k - 1; j++) {
long target = cur + lo;
int idx = lowerBound(nums, target);
if (idx == nums.length || nums[idx] > end) {
ok = false;
break;
}
cur = nums[idx];
}
if (ok) {
return true;
}
}
return false;
}
private int lowerBound(long[] arr, long target) {
int left = 0, right = arr.length;
while (left < right) {
int mid = (left + right) >>> 1;
if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
}class Solution {
public:
int maxDistance(int side, vector<vector<int>>& points, int k) {
vector<long long> nums;
for (auto& p : points) {
int x = p[0];
int y = p[1];
if (x == 0) {
nums.push_back((long long) y);
} else if (y == side) {
nums.push_back((long long) side + x);
} else if (x == side) {
nums.push_back((long long) side * 3 - y);
} else {
nums.push_back((long long) side * 4 - x);
}
}
sort(nums.begin(), nums.end());
auto check = [&](int lo) -> bool {
long long total = (long long) side * 4;
for (long long start : nums) {
long long end = start + total - lo;
long long cur = start;
bool ok = true;
for (int i = 0; i < k - 1; ++i) {
auto it = lower_bound(nums.begin(), nums.end(), cur + lo);
if (it == nums.end() || *it > end) {
ok = false;
break;
}
cur = *it;
}
if (ok) {
return true;
}
}
return false;
};
int l = 1, r = side;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (check(mid)) {
l = mid;
} else {
r = mid - 1;
}
}
return l;
}
};function maxDistance(side: number, points: number[][], k: number): number {
const nums: number[] = [];
for (const [x, y] of points) {
if (x === 0) {
nums.push(y);
} else if (y === side) {
nums.push(side + x);
} else if (x === side) {
nums.push(side * 3 - y);
} else {
nums.push(side * 4 - x);
}
}
nums.sort((a, b) => a - b);
const check = (lo: number): boolean => {
const total = side * 4;
for (const start of nums) {
const end = start + total - lo;
let cur = start;
let ok = true;
for (let i = 0; i < k - 1; i++) {
const j = _.sortedIndex(nums, cur + lo);
if (j === nums.length || nums[j] > end) {
ok = false;
break;
}
cur = nums[j];
}
if (ok) {
return true;
}
}
return false;
};
let l = 1,
r = side;
while (l < r) {
const mid = (l + r + 1) >> 1;
if (check(mid)) {
l = mid;
} else {
r = mid - 1;
}
}
return l;
}func maxDistance(side int, points [][]int, k int) int {
nums := make([]int64, 0, len(points))
for _, p := range points {
x, y := int64(p[0]), int64(p[1])
s := int64(side)
if x == 0 {
nums = append(nums, y)
} else if y == s {
nums = append(nums, s+x)
} else if x == s {
nums = append(nums, s*3-y)
} else {
nums = append(nums, s*4-x)
}
}
sort.Slice(nums, func(i, j int) bool {
return nums[i] < nums[j]
})
check := func(lo int) bool {
total := int64(side) * 4
l64 := int64(lo)
for _, start := range nums {
end := start + total - l64
cur := start
ok := true
for i := 0; i < k-1; i++ {
target := cur + l64
idx := sort.Search(len(nums), func(i int) bool {
return nums[i] >= target
})
if idx == len(nums) || nums[idx] > end {
ok = false
break
}
cur = nums[idx]
}
if ok {
return true
}
}
return false
}
l, r := 1, side
for l < r {
mid := (l + r + 1) >> 1
if check(mid) {
l = mid
} else {
r = mid - 1
}
}
return l
}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 |
Frequently asked questions
Is Maximize the Distance Between Points on a Square easy or hard?
Maximize the Distance Between Points on a Square is categorized as a Hard problem because it combines geometry preprocessing, circular array handling, and binary search on the answer. Recognizing the perimeter mapping and feasibility check pattern is the main challenge.
Maximize the Distance Between Points on a Square Python/Java solution
Implement the solution by mapping each point to its perimeter coordinate, sorting the array, and applying binary search on the minimum distance. During each check, greedily place points while ensuring at least the candidate spacing. This implementation works consistently across Python, Java, C++, and Go with the same algorithmic structure.
How to solve Maximize the Distance Between Points on a Square in O(n log n)?
First convert each point on the square boundary into a single perimeter distance measured from a fixed corner. Sort these values and binary search the maximum minimum distance between chosen points. For each candidate distance, greedily pick points while maintaining the spacing constraint and simulate circular wraparound by duplicating the perimeter array.
What is the best approach for Maximize the Distance Between Points on a Square?
The most efficient approach maps each boundary point to its position along the square’s perimeter, sorts those positions, and performs binary search on the minimum allowed distance. A greedy feasibility check verifies whether k points can be placed with at least that spacing. This reduces the problem to O(n log n + n log P) time where P is the perimeter.
Is Maximize the Distance Between Points on a Square asked at Google/Amazon/Meta?
Problems involving maximizing minimum distance using binary search and greedy checks appear frequently in interviews at companies like Google, Amazon, and Meta. Variants include aggressive cows, router placement, and circular spacing problems, all using the same binary search on answer pattern.
What data structure is used in Maximize the Distance Between Points on a Square?
The core data structure is a sorted array of perimeter positions. Binary search is applied on the answer space, and a greedy scan over the array verifies feasibility. Geometry is only used during preprocessing to convert 2D coordinates into 1D perimeter distances.
What is the time complexity of Maximize the Distance Between Points on a Square?
The optimal algorithm runs in O(n log n + n log P). Sorting the perimeter positions takes O(n log n), and binary searching the answer performs O(log P) iterations with an O(n) greedy feasibility check each time. Space complexity is O(n) for storing mapped positions.