4 <= k <= min(25, points.length)

Solution

Method 1 – Binary Search with Greedy Placement

Intuition

To maximize the minimum Manhattan distance between any two selected points, we can use binary search on the answer. For each candidate distance, we greedily try to select points such that every new point is at least that far from all previously selected points.

Approach

Map all points to a 1D representation of their position along the square's boundary (since all points are on the boundary, the Manhattan distance between two points is the distance along the boundary).
Sort the mapped positions.
Use binary search for the answer between 0 and the perimeter of the square.
For each mid value, try to greedily select points such that each is at least mid away from the previous selected point (wrapping around the perimeter if needed).
If possible to select k points, try a larger value; otherwise, try smaller.
Return the largest value for which it is possible.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int maximizeDistance(int side, vector<vector<int>>& points, int k) {\n        int n = points.size();\n        vector<int> pos;\n        int perim = 4 * side;\n        for (auto& p : points) {\n            int x = p[0], y = p[1];\n            if (y == 0) pos.push_back(x);\n            else if (x == side) pos.push_back(side + y);\n            else if (y == side) pos.push_back(3 * side - x);\n            else pos.push_back(4 * side - y);\n        }\n        sort(pos.begin(), pos.end());\n        int l = 0, r = perim, ans = 0;\n        while (l <= r) {\n            int m = (l + r) / 2;\n            int cnt = 1, last = pos[0];\n            for (int i = 1; i < n; ++i) {\n                if (pos[i] - last >= m) {\n                    cnt++;\n                    last = pos[i];\n                }\n            }\n            if (perim - last + pos[0] >= m) cnt++;\n            if (cnt >= k) { ans = m; l = m + 1; }\n            else r = m - 1;\n        }\n        return ans;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    int</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> maximizeDistance</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> side</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">, </span><span style=\"color:#6F42C1;--shiki-dark

Related Tags