commit 86003e3f3bdee99c26b48c7377b665715cd56cb2
parent 6cb05c1fb3abea9ff6efc61065bae148092394d9
Author: Jack Sangdahl <jack@pngu.org>
Date: Fri, 24 Apr 2026 21:08:00 -0600
3464. maximise the distance between points on a square
Diffstat:
2 files changed, 171 insertions(+), 0 deletions(-)
diff --git a/maximise_dist_point_square.c b/maximise_dist_point_square.c
@@ -0,0 +1,113 @@
+// 3464. Maximize the Distance Between Points on a Square
+#include "leetcode.h"
+
+/*
+ * 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] = [x_i, y_i]' 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 in maximised.
+ */
+
+int cmp(const void *a, const void *b) {
+ long long aa = *(long long *)a;
+ long long bb = *(long long *)b;
+ if (aa < bb)
+ return -1;
+ else if (aa > bb)
+ return 1;
+ else
+ return 0;
+}
+
+bool can_place(long long d, int k, int n, long long *ext, long long l) {
+ for (int start = 0; start < n; start++) {
+ int curr = start, limit = start + n;
+ long long prev = ext[start];
+ bool valid = true;
+ for (int step = 1; step < k; step++) {
+ long long target = prev + d;
+ int low = curr + 1, high = limit;
+ while (low < high) {
+ int mid = (low + high) / 2;
+ if (ext[mid] < target)
+ low = mid + 1;
+ else
+ high = mid;
+ }
+ if (low == limit) {
+ valid = false;
+ break;
+ }
+ curr = low;
+ prev = ext[curr];
+ }
+ if (valid && (ext[start] + l - prev >= d))
+ return true;
+ }
+ return false;
+}
+
+int maxDistance(int side, int **points, int pointsSize, int *pointsColSize,
+ int k) {
+ int n = pointsSize;
+ long long *pos = (long long *)malloc(n * sizeof(long long));
+ for (int i = 0; i < n; i++) {
+ int x = points[i][0], y = points[i][1];
+ long long p;
+ if (!y)
+ p = x;
+ else if (x == side)
+ p = side + y;
+ else if (y == side)
+ p = 2LL * side + (side - x);
+ else
+ p = 3LL * side + (side - y);
+ pos[i] = p;
+ }
+ qsort(pos, n, sizeof(long long), cmp);
+ long long l = 2LL * side;
+ int total = n * 2;
+ long long *ext = (long long *)malloc(total * sizeof(long long));
+ for (int i = 0; i < n; i++) {
+ ext[i] = pos[i];
+ ext[i + n] = pos[i] + l;
+ }
+ long long low = 0, high = 2LL * side;
+ while (low < high) {
+ long long mid = (low + high + 1) / 2;
+ if (can_place(mid, k, n, ext, l))
+ low = mid;
+ else
+ high = mid - 1;
+ }
+ free(pos);
+ free(ext);
+ return (int)low;
+}
+
+int main() {
+ int p1i[4][2] = {{0, 2}, {2, 0}, {2, 2}, {0, 0}};
+ int p2i[5][2] = {{0, 0}, {1, 2}, {2, 0}, {2, 2}, {2, 1}};
+ int p3i[7][2] = {{0, 0}, {0, 1}, {0, 2}, {1, 2}, {2, 0}, {2, 2}, {2, 1}};
+ struct two_d_arr *p1 =
+ two_d_arr_init(ARRAY_SIZE(p1i), ARRAY_SIZE(p1i[0]), p1i);
+ struct two_d_arr *p2 =
+ two_d_arr_init(ARRAY_SIZE(p1i), ARRAY_SIZE(p1i[0]), p1i);
+ struct two_d_arr *p3 =
+ two_d_arr_init(ARRAY_SIZE(p1i), ARRAY_SIZE(p1i[0]), p1i);
+ int r1 = maxDistance(2, p1->arr, p1->row_size, p1->col_size, 4);
+ int r2 = maxDistance(2, p2->arr, p2->row_size, p2->col_size, 4);
+ int r3 = maxDistance(2, p3->arr, p3->row_size, p3->col_size, 5);
+ printf("%d\n", r1);
+ assert(r1 == 2);
+ printf("%d\n", r2);
+ assert(r2 == 1);
+ printf("%d\n", r3);
+ assert(r3 == 1);
+ two_d_arr_free(p1);
+ two_d_arr_free(p2);
+ two_d_arr_free(p3);
+}
diff --git a/maximise_dist_point_square.py b/maximise_dist_point_square.py
@@ -0,0 +1,58 @@
+# 3464. Maximize the Distance Between Points on a Square
+from bisect import bisect_left
+from typing import List
+
+"""
+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] = [x_i, y_i]' 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 in maximised.
+"""
+
+
+class Solution:
+ def maxDistance(self, side: int, points: List[List[int]], k: int) -> int:
+ def flatten(p):
+ x, y = p
+ if y == 0:
+ return x
+ if x == side:
+ return side + y
+ if y == side:
+ return 3 * side - x
+ if x == 0:
+ return 4 * side - y
+
+ def can_place(min_dist):
+ for i, num in enumerate(arr):
+ ptr, cnt = i, 1
+ while cnt < k:
+ j = bisect_left(arr, arr[ptr] + min_dist)
+ if j == len(points):
+ break
+ ptr = j
+ cnt += 1
+ if min_dist + arr[ptr] > num + 4 * side:
+ cnt = 0
+ break
+ if cnt == k:
+ return False
+ return True
+
+ arr = sorted(map(flatten, points))
+ first_invalid = bisect_left(range(0, side + 1), True, key=can_place)
+ return first_invalid - 1
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.maxDistance(side=2, points=[[0, 2], [2, 0], [2, 2], [0, 0]], k=4))
+ print(obj.maxDistance(side=2, points=[[0, 0], [1, 2], [2, 0], [2, 2], [2, 1]], k=4))
+ print(
+ obj.maxDistance(
+ side=2, points=[[0, 0], [0, 1], [0, 2], [1, 2], [2, 0], [2, 2], [2, 1]], k=5
+ )
+ )
