Welcome to Subscribe On Youtube
3464. Maximize the Distance Between Points on a Square
Description
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)
Solutions
Solution 1
-
class 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; } }; -
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 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 } -
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; }