Skip to content

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 <= 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.
  • 4 <= k <= min(25, points.length)

Solutions

Solution 1: Binary Search + Coordinate Mapping + Greedy

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 \text{side})\). The mapping rules are as follows:

  • If \(x = 0\), the mapped value is \(y\);
  • If \(y = \text{side}\), the mapped value is \(\text{side} + x\);
  • If \(x = \text{side}\), the mapped value is \(3 \times \text{side} - y\);
  • Otherwise, the mapped value is \(4 \times \text{side} - x\).

After mapping, sort all the points to obtain the array \(\textit{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 \(\textit{lo}\), we use a \(\textit{check}\) function to verify its feasibility:

  • Iterate through each point in \(\textit{nums}\) as the starting point \(\textit{start}\).
  • The endpoint for selecting points is \(\textit{end} = \textit{start} + 4 \times \text{side} - \textit{lo}\), ensuring that the wrap-around distance from the last selected point back to \(\textit{start}\) is at least \(\textit{lo}\).
  • Then, greedily perform \(k-1\) jumps, each time using binary search to quickly locate the next point that is at least \(\textit{lo}\) away from the current position.
  • If it is possible to select \(k\) points within the \(\textit{end}\) limit, then the distance \(\textit{lo}\) is feasible.

The time complexity is \(O(n \log (\text{side}) \cdot n \log n)\) and the space complexity is \(O(n)\), where \(n\) is the length of the \(\textit{points}\) array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
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;
}

Comments