3464. Maximize the Distance Between Points on a Square

/**
 * Problem: LeetCode 3464 - Maximize the Distance Between Points on a Square
 * Difficulty: Hard
 * Language: Java
 * Author: CodeByTushu
 */
import java.util.Arrays;

class Solution {
    public int maxDistance(int side, int[][] points, int k) {
        // Step 1: Convert boundary points into 1D perimeter distance
        int n = points.length;
        long[] arr = new long[n];
        
        for (int i = 0; i < n; i++) {
            int x = points[i][0];
            int y = points[i][1];
            
            if (x == 0) {
                arr[i] = y;
            } else if (y == side) {
                arr[i] = (long) side + x;
            } else if (x == side) {
                arr[i] = 3L * side - y;
            } else {
                arr[i] = 4L * side - x;
            }
        }
        
        Arrays.sort(arr);
        
        long perimeter = 4L * side;
        long[] arrExt = new long[2 * n];
        for (int i = 0; i < n; i++) {
            arrExt[i] = arr[i];
            arrExt[i + n] = arr[i] + perimeter;
        }
        
        // Binary search answer in [1, side]
        long left = 1, right = side, ans = 0;
        while (left <= right) {
            long mid = left + (right - left) / 2;
            if (canPlace(arr, arrExt, n, k, mid, perimeter)) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return (int) ans;
    }
    
    private boolean canPlace(long[] arr, long[] arrExt, int n, int k, long d, long perimeter) {
        for (int i = 0; i < n; i++) {
            long curr = arr[i];
            int count = 1;
            int idx = i;
            
            for (int step = 1; step < k; step++) {
                long target = curr + d;
                int l = idx + 1, r = i + n - 1;
                int found = -1;
                
                while (l <= r) {
                    int mid = l + (r - l) / 2;
                    if (arrExt[mid] >= target) {
                        found = mid;
                        r = mid - 1;
                    } else {
                        l = mid + 1;
                    }
                }
                
                if (found == -1) break;
                curr = arrExt[found];
                idx = found;
                count++;
            }
            
            if (count == k && (arr[i] + perimeter - curr) >= d) {
                return true;
            }
        }
        return false;
    }
}

"""
Problem: LeetCode 3464 - Maximize the Distance Between Points on a Square
Difficulty: Hard
Language: Python
Author: CodeByTushu
"""
from typing import List
from bisect import bisect_left


class Solution:
    def maxDistance(self, side: int, points: List[List[int]], k: int) -> int:
        n = len(points)
        arr = [0] * n

        # Convert boundary points into 1D perimeter distance
        for i, (x, y) in enumerate(points):
            if x == 0:
                arr[i] = y
            elif y == side:
                arr[i] = side + x
            elif x == side:
                arr[i] = 3 * side - y
            else:
                arr[i] = 4 * side - x

        arr.sort()

        perimeter = 4 * side
        arr_ext = arr + [val + perimeter for val in arr]

        def can_place(d: int) -> bool:
            for i in range(n):
                curr = arr[i]
                count = 1
                idx = i

                for _ in range(k - 1):
                    target = curr + d
                    found = bisect_left(arr_ext, target, idx + 1, i + n)
                    if found >= i + n:
                        break
                    curr = arr_ext[found]
                    idx = found
                    count += 1

                if count == k and (arr[i] + perimeter - curr) >= d:
                    return True
            return False

        left, right = 1, side
        ans = 0

        while left <= right:
            mid = (left + right) // 2
            if can_place(mid):
                ans = mid
                left = mid + 1
            else:
                right = mid - 1

        return ans

/**
 * Problem: LeetCode 3464 - Maximize the Distance Between Points on a Square
 * Difficulty: Hard
 * Language: C++
 * Author: CodeByTushu
 */
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int maxDistance(int side, vector<vector<int>>& points, int k) {
        int n = points.size();
        vector<long long> arr(n);
        
        for (int i = 0; i < n; ++i) {
            long long x = points[i][0];
            long long y = points[i][1];
            
            if (x == 0) {
                arr[i] = y;
            } else if (y == side) {
                arr[i] = (long long)side + x;
            } else if (x == side) {
                arr[i] = 3LL * side - y;
            } else {
                arr[i] = 4LL * side - x;
            }
        }
        
        sort(arr.begin(), arr.end());
        
        long long perimeter = 4LL * side;
        vector<long long> arrExt(2 * n);
        for (int i = 0; i < n; ++i) {
            arrExt[i] = arr[i];
            arrExt[i + n] = arr[i] + perimeter;
        }
        
        auto canPlace = [&](long long d) -> bool {
            for (int i = 0; i < n; ++i) {
                long long curr = arr[i];
                int count = 1;
                int idx = i;
                
                for (int step = 1; step < k; ++step) {
                    long long target = curr + d;
                    auto it = lower_bound(arrExt.begin() + idx + 1, arrExt.begin() + i + n, target);
                    if (it == arrExt.begin() + i + n) break;
                    
                    idx = it - arrExt.begin();
                    curr = *it;
                    count++;
                }
                
                if (count == k && (arr[i] + perimeter - curr) >= d) {
                    return true;
                }
            }
            return false;
        };
        
        long long left = 1, right = side, ans = 0;
        while (left <= right) {
            long long mid = left + (right - left) / 2;
            if (canPlace(mid)) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return ans;
    }
};

/**
 * Problem: LeetCode 3464 - Maximize the Distance Between Points on a Square
 * Difficulty: Hard
 * Language: JavaScript
 * Author: CodeByTushu
 */
/**
 * @param {number} side
 * @param {number[][]} points
 * @param {number} k
 * @return {number}
 */
var maxDistance = function(side, points, k) {
    const n = points.length;
    const arr = new Float64Array(n);

    // Step 1: Convert boundary points into 1D perimeter distance
    for (let i = 0; i < n; i++) {
        const x = points[i][0];
        const y = points[i][1];

        if (x === 0) {
            arr[i] = y;
        } else if (y === side) {
            arr[i] = side + x;
        } else if (x === side) {
            arr[i] = 3 * side - y;
        } else {
            arr[i] = 4 * side - x;
        }
    }

    arr.sort();

    const perimeter = 4 * side;
    const arrExt = new Float64Array(2 * n);
    for (let i = 0; i < n; i++) {
        arrExt[i] = arr[i];
        arrExt[i + n] = arr[i] + perimeter;
    }

    function canPlace(d) {
        for (let i = 0; i < n; i++) {
            let curr = arr[i];
            let count = 1;
            let idx = i;

            for (let step = 1; step < k; step++) {
                const target = curr + d;
                let l = idx + 1, r = i + n - 1;
                let found = -1;

                while (l <= r) {
                    const mid = (l + r) >> 1;
                    if (arrExt[mid] >= target) {
                        found = mid;
                        r = mid - 1;
                    } else {
                        l = mid + 1;
                    }
                }

                if (found === -1) break;
                curr = arrExt[found];
                idx = found;
                count++;
            }

            if (count === k && (arr[i] + perimeter - curr) >= d) {
                return true;
            }
        }
        return false;
    }

    let left = 1, right = side, ans = 0;
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (canPlace(mid)) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return ans;
};