Daily LeetCode - by Vítor Belim

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] = [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 is maximized.

Return the maximum possible minimum Manhattan distance between the selected k points.

The Manhattan Distance between two cells (x_i, y_i) and (x_j, y_j) is |x_i - x_j| + |y_i - y_j|.

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 <= 10⁹
4 <= points.length <= min(4 * side, 15 * 10³)
points[i] == [x_i, y_i]
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

This solution places k points on a square's perimeter to maximize the minimum distance between consecutive points. It first converts 2D edge coordinates into 1D perimeter positions (treating the square's outline as a line), then uses binary search on the answer combined with a greedy validation: for each candidate minimum distance (limit), the check() function tries to place k points such that each is at least limit units apart by greedily picking the earliest valid position. The lowerBound() helper efficiently finds the first point at or beyond a target distance using binary search on the sorted positions.

Language: javascript(2026-04-25 08:41)DONE

CPU Performance11.11%

Memory Performance66.67%

/**
 * @param {number} side
 * @param {number[][]} points
 * @param {number} k
 * @return {number}
 */
var maxDistance = function (side, points, k) {
    const arr = [];

    for (const [x, y] of points) {
        if (x === 0) {
            arr.push(y);
        } else if (y === side) {
            arr.push(side + x);
        } else if (x === side) {
            arr.push(side * 3 - y);
        } else {
            arr.push(side * 4 - x);
        }
    }

    arr.sort((a, b) => a - b);

    const lowerBound = (target) => {
        let left = 0;
        let right = arr.length;

        while (left < right) {
            const mid = Math.floor((left + right) / 2);

            if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return left;
    };

    const check = (limit) => {
        const perimeter = side * 4;

        for (const start of arr) {
            const end = start + perimeter - limit;
            let cur = start;

            for (let i = 0; i < k - 1; i++) {
                const idx = lowerBound(cur + limit);

                if (idx === arr.length || arr[idx] > end) {
                    cur = -1;
                    break;
                }

                cur = arr[idx];
            }

            if (cur >= 0) {
                return true;
            }
        }

        return false;
    };

    let lo = 1;
    let hi = side;
    let ans = 0;

    while (lo <= hi) {
        const mid = Math.floor((lo + hi) / 2);

        if (check(mid)) {
            lo = mid + 1;
            ans = mid;
        } else {
            hi = mid - 1;
        }
    }

    return ans;
};

Description

Solutions

AI Explanation