LeetCode 3464: Maximize the Distance Between Points on a Square (Perimeter Mapping + Binary Search)
LeetCode 3464Binary SearchGreedyToday we solve LeetCode 3464 - Maximize the Distance Between Points on a Square.
Source: https://leetcode.com/problems/maximize-the-distance-between-points-on-a-square/
English
Problem Summary
Given boundary points on a square and an integer k, pick k points so the minimum circular perimeter distance between adjacent chosen points is maximized.
Key Insight
Map every boundary point to a 1D coordinate on the square perimeter [0, 4*side). Then the task becomes selecting k positions on a circle to maximize the minimum gap.
Algorithm
- Convert each point (x,y) to perimeter index in clockwise order.
- Sort mapped positions.
- Binary search answer d (minimum allowed gap).
- Feasibility check: duplicate array with +perimeter, greedy jump by d using lower_bound for k picks, and ensure wrap-around final gap is also at least d.
Complexity Analysis
Time: O(n log n + n log P log n), where P = 4*side.
Space: O(n).
Common Pitfalls
- Incorrect edge mapping order on 4 sides.
- Forgetting circular wrap-around constraint for the last selected point.
- Binary search upper bound set too large.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
import java.util.*;
class Solution {
public int maxDistance(int side, int[][] points, int k) {
long per = 4L * side;
int n = points.length;
long[] a = new long[n];
for (int i = 0; i < n; i++) a[i] = map(points[i][0], points[i][1], side);
Arrays.sort(a);
long lo = 0, hi = per / k;
while (lo < hi) {
long mid = (lo + hi + 1) >> 1;
if (ok(a, per, k, mid)) lo = mid;
else hi = mid - 1;
}
return (int) lo;
}
private boolean ok(long[] a, long per, int k, long d) {
int n = a.length;
long[] b = new long[2 * n];
for (int i = 0; i < n; i++) {
b[i] = a[i];
b[i + n] = a[i] + per;
}
for (int s = 0; s < n; s++) {
long first = b[s], cur = b[s];
int idx = s, cnt = 1;
while (cnt < k) {
long need = cur + d;
int j = lowerBound(b, need, idx + 1, s + n);
if (j >= s + n) break;
cur = b[j];
idx = j;
cnt++;
}
if (cnt == k && first + per - cur >= d) return true;
}
return false;
}
private int lowerBound(long[] a, long target, int l, int r) {
int lo = l, hi = r;
while (lo < hi) {
int m = (lo + hi) >> 1;
if (a[m] >= target) hi = m;
else lo = m + 1;
}
return lo;
}
private long map(int x, int y, int s) {
if (y == 0) return x;
if (x == s) return (long) s + y;
if (y == s) return 3L * s - x;
return 4L * s - y;
}
}import "sort"
func maxDistance(side int, points [][]int, k int) int {
per := int64(4 * side)
n := len(points)
a := make([]int64, n)
for i, p := range points {
a[i] = mapPos(p[0], p[1], side)
}
sort.Slice(a, func(i, j int) bool { return a[i] < a[j] })
lo, hi := int64(0), per/int64(k)
for lo < hi {
mid := (lo + hi + 1) / 2
if ok(a, per, k, mid) {
lo = mid
} else {
hi = mid - 1
}
}
return int(lo)
}
func ok(a []int64, per int64, k int, d int64) bool {
n := len(a)
b := make([]int64, 2*n)
for i := 0; i < n; i++ {
b[i] = a[i]
b[i+n] = a[i] + per
}
for s := 0; s < n; s++ {
first, cur := b[s], b[s]
idx, cnt := s, 1
for cnt < k {
need := cur + d
j := lowerBound(b, need, idx+1, s+n)
if j >= s+n {
break
}
cur = b[j]
idx = j
cnt++
}
if cnt == k && first+per-cur >= d {
return true
}
}
return false
}
func lowerBound(a []int64, target int64, l, r int) int {
lo, hi := l, r
for lo < hi {
m := (lo + hi) / 2
if a[m] >= target {
hi = m
} else {
lo = m + 1
}
}
return lo
}
func mapPos(x, y, s int) int64 {
if y == 0 {
return int64(x)
}
if x == s {
return int64(s + y)
}
if y == s {
return int64(3*s - x)
}
return int64(4*s - y)
}class Solution {
public:
int maxDistance(int side, vector<vector<int>>& points, int k) {
long long per = 4LL * side;
vector<long long> a;
for (auto &p : points) a.push_back(mapPos(p[0], p[1], side));
sort(a.begin(), a.end());
long long lo = 0, hi = per / k;
while (lo < hi) {
long long mid = (lo + hi + 1) >> 1;
if (ok(a, per, k, mid)) lo = mid;
else hi = mid - 1;
}
return (int)lo;
}
bool ok(const vector<long long>& a, long long per, int k, long long d) {
int n = (int)a.size();
vector<long long> b(2 * n);
for (int i = 0; i < n; i++) {
b[i] = a[i];
b[i + n] = a[i] + per;
}
for (int s = 0; s < n; s++) {
long long first = b[s], cur = b[s];
int idx = s, cnt = 1;
while (cnt < k) {
long long need = cur + d;
int j = lower_bound(b.begin() + idx + 1, b.begin() + s + n, need) - b.begin();
if (j >= s + n) break;
cur = b[j];
idx = j;
cnt++;
}
if (cnt == k && first + per - cur >= d) return true;
}
return false;
}
long long mapPos(int x, int y, int s) {
if (y == 0) return x;
if (x == s) return 1LL * s + y;
if (y == s) return 3LL * s - x;
return 4LL * s - y;
}
};from bisect import bisect_left
class Solution:
def maxDistance(self, side: int, points: list[list[int]], k: int) -> int:
per = 4 * side
arr = sorted(self._map(x, y, side) for x, y in points)
def ok(d: int) -> bool:
n = len(arr)
b = arr + [x + per for x in arr]
for s in range(n):
first = cur = b[s]
idx = s
cnt = 1
while cnt < k:
need = cur + d
j = bisect_left(b, need, idx + 1, s + n)
if j >= s + n:
break
cur = b[j]
idx = j
cnt += 1
if cnt == k and first + per - cur >= d:
return True
return False
lo, hi = 0, per // k
while lo < hi:
mid = (lo + hi + 1) // 2
if ok(mid):
lo = mid
else:
hi = mid - 1
return lo
def _map(self, x: int, y: int, s: int) -> int:
if y == 0:
return x
if x == s:
return s + y
if y == s:
return 3 * s - x
return 4 * s - yvar maxDistance = function(side, points, k) {
const per = 4 * side;
const arr = points.map(([x, y]) => mapPos(x, y, side)).sort((a, b) => a - b);
const ok = (d) => {
const n = arr.length;
const b = arr.concat(arr.map(x => x + per));
for (let s = 0; s < n; s++) {
let first = b[s], cur = b[s], idx = s, cnt = 1;
while (cnt < k) {
const need = cur + d;
const j = lowerBound(b, need, idx + 1, s + n);
if (j >= s + n) break;
cur = b[j];
idx = j;
cnt++;
}
if (cnt === k && first + per - cur >= d) return true;
}
return false;
};
let lo = 0, hi = Math.floor(per / k);
while (lo < hi) {
const mid = Math.floor((lo + hi + 1) / 2);
if (ok(mid)) lo = mid;
else hi = mid - 1;
}
return lo;
};
function lowerBound(a, target, l, r) {
let lo = l, hi = r;
while (lo < hi) {
const m = (lo + hi) >> 1;
if (a[m] >= target) hi = m;
else lo = m + 1;
}
return lo;
}
function mapPos(x, y, s) {
if (y === 0) return x;
if (x === s) return s + y;
if (y === s) return 3 * s - x;
return 4 * s - y;
}中文
题目概述
给定正方形边界上的若干点和整数 k，从中选出 k 个点，使得按边界环形顺序相邻被选点的最小距离最大。
核心思路
把每个边界点映射到周长坐标 [0,4*side)，问题就变成圆环上一维选点最大化最小间距。然后对答案做二分。
算法步骤
- 按顺时针将点映射到周长坐标并排序。
- 二分最小间距 d。
- 可行性检查：数组复制一份并加上周长，枚举起点后用贪心 + lower_bound 跳到下一个至少间距 d 的点，选满 k 个后再检查首尾环形间距。
复杂度分析
时间复杂度：O(n log n + n log P log n)，其中 P=4*side。
空间复杂度：O(n)。
常见陷阱
- 四条边映射顺序写错。
- 忘了校验最后一个点回到第一个点的环形间距。
- 二分上界设置不合理导致超时或错误。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
import java.util.*;
class Solution {
public int maxDistance(int side, int[][] points, int k) {
long per = 4L * side;
int n = points.length;
long[] a = new long[n];
for (int i = 0; i < n; i++) a[i] = map(points[i][0], points[i][1], side);
Arrays.sort(a);
long lo = 0, hi = per / k;
while (lo < hi) {
long mid = (lo + hi + 1) >> 1;
if (ok(a, per, k, mid)) lo = mid;
else hi = mid - 1;
}
return (int) lo;
}
private boolean ok(long[] a, long per, int k, long d) {
int n = a.length;
long[] b = new long[2 * n];
for (int i = 0; i < n; i++) {
b[i] = a[i];
b[i + n] = a[i] + per;
}
for (int s = 0; s < n; s++) {
long first = b[s], cur = b[s];
int idx = s, cnt = 1;
while (cnt < k) {
long need = cur + d;
int j = lowerBound(b, need, idx + 1, s + n);
if (j >= s + n) break;
cur = b[j];
idx = j;
cnt++;
}
if (cnt == k && first + per - cur >= d) return true;
}
return false;
}
private int lowerBound(long[] a, long target, int l, int r) {
int lo = l, hi = r;
while (lo < hi) {
int m = (lo + hi) >> 1;
if (a[m] >= target) hi = m;
else lo = m + 1;
}
return lo;
}
private long map(int x, int y, int s) {
if (y == 0) return x;
if (x == s) return (long) s + y;
if (y == s) return 3L * s - x;
return 4L * s - y;
}
}import "sort"
func maxDistance(side int, points [][]int, k int) int {
per := int64(4 * side)
n := len(points)
a := make([]int64, n)
for i, p := range points {
a[i] = mapPos(p[0], p[1], side)
}
sort.Slice(a, func(i, j int) bool { return a[i] < a[j] })
lo, hi := int64(0), per/int64(k)
for lo < hi {
mid := (lo + hi + 1) / 2
if ok(a, per, k, mid) {
lo = mid
} else {
hi = mid - 1
}
}
return int(lo)
}
func ok(a []int64, per int64, k int, d int64) bool {
n := len(a)
b := make([]int64, 2*n)
for i := 0; i < n; i++ {
b[i] = a[i]
b[i+n] = a[i] + per
}
for s := 0; s < n; s++ {
first, cur := b[s], b[s]
idx, cnt := s, 1
for cnt < k {
need := cur + d
j := lowerBound(b, need, idx+1, s+n)
if j >= s+n {
break
}
cur = b[j]
idx = j
cnt++
}
if cnt == k && first+per-cur >= d {
return true
}
}
return false
}
func lowerBound(a []int64, target int64, l, r int) int {
lo, hi := l, r
for lo < hi {
m := (lo + hi) / 2
if a[m] >= target {
hi = m
} else {
lo = m + 1
}
}
return lo
}
func mapPos(x, y, s int) int64 {
if y == 0 {
return int64(x)
}
if x == s {
return int64(s + y)
}
if y == s {
return int64(3*s - x)
}
return int64(4*s - y)
}class Solution {
public:
int maxDistance(int side, vector<vector<int>>& points, int k) {
long long per = 4LL * side;
vector<long long> a;
for (auto &p : points) a.push_back(mapPos(p[0], p[1], side));
sort(a.begin(), a.end());
long long lo = 0, hi = per / k;
while (lo < hi) {
long long mid = (lo + hi + 1) >> 1;
if (ok(a, per, k, mid)) lo = mid;
else hi = mid - 1;
}
return (int)lo;
}
bool ok(const vector<long long>& a, long long per, int k, long long d) {
int n = (int)a.size();
vector<long long> b(2 * n);
for (int i = 0; i < n; i++) {
b[i] = a[i];
b[i + n] = a[i] + per;
}
for (int s = 0; s < n; s++) {
long long first = b[s], cur = b[s];
int idx = s, cnt = 1;
while (cnt < k) {
long long need = cur + d;
int j = lower_bound(b.begin() + idx + 1, b.begin() + s + n, need) - b.begin();
if (j >= s + n) break;
cur = b[j];
idx = j;
cnt++;
}
if (cnt == k && first + per - cur >= d) return true;
}
return false;
}
long long mapPos(int x, int y, int s) {
if (y == 0) return x;
if (x == s) return 1LL * s + y;
if (y == s) return 3LL * s - x;
return 4LL * s - y;
}
};from bisect import bisect_left
class Solution:
def maxDistance(self, side: int, points: list[list[int]], k: int) -> int:
per = 4 * side
arr = sorted(self._map(x, y, side) for x, y in points)
def ok(d: int) -> bool:
n = len(arr)
b = arr + [x + per for x in arr]
for s in range(n):
first = cur = b[s]
idx = s
cnt = 1
while cnt < k:
need = cur + d
j = bisect_left(b, need, idx + 1, s + n)
if j >= s + n:
break
cur = b[j]
idx = j
cnt += 1
if cnt == k and first + per - cur >= d:
return True
return False
lo, hi = 0, per // k
while lo < hi:
mid = (lo + hi + 1) // 2
if ok(mid):
lo = mid
else:
hi = mid - 1
return lo
def _map(self, x: int, y: int, s: int) -> int:
if y == 0:
return x
if x == s:
return s + y
if y == s:
return 3 * s - x
return 4 * s - yvar maxDistance = function(side, points, k) {
const per = 4 * side;
const arr = points.map(([x, y]) => mapPos(x, y, side)).sort((a, b) => a - b);
const ok = (d) => {
const n = arr.length;
const b = arr.concat(arr.map(x => x + per));
for (let s = 0; s < n; s++) {
let first = b[s], cur = b[s], idx = s, cnt = 1;
while (cnt < k) {
const need = cur + d;
const j = lowerBound(b, need, idx + 1, s + n);
if (j >= s + n) break;
cur = b[j];
idx = j;
cnt++;
}
if (cnt === k && first + per - cur >= d) return true;
}
return false;
};
let lo = 0, hi = Math.floor(per / k);
while (lo < hi) {
const mid = Math.floor((lo + hi + 1) / 2);
if (ok(mid)) lo = mid;
else hi = mid - 1;
}
return lo;
};
function lowerBound(a, target, l, r) {
let lo = l, hi = r;
while (lo < hi) {
const m = (lo + hi) >> 1;
if (a[m] >= target) hi = m;
else lo = m + 1;
}
return lo;
}
function mapPos(x, y, s) {
if (y === 0) return x;
if (x === s) return s + y;
if (y === s) return 3 * s - x;
return 4 * s - y;
}
Comments