3464. Maximize the Distance Between Points on a Square

Time: O(m log m + m log side)

Space: O(m)

Intuition

All points lie on the square perimeter, so we can linearize them in clockwise order and turn geometry into an ordered sequence problem. Then we binary-search the answer d: if we can pick k points with minimum required Manhattan separation d, any smaller d is also feasible. The core is a linear feasibility check that grows the longest valid chain ending at each point.

Algorithm

1Partition boundary points into left/top/right/bottom edges and sort each edge in traversal order, then concatenate to build clockwise order.
2Binary-search d in [0, side]. For each mid, run IsValidDistance to test feasibility.
3In IsValidDistance, maintain deque states of the form (start point, end point, chain length).
4For each new point p, pop deque front states whose end point is far enough from p (distance >= d). Those states are candidates to extend by p.
5Among extendable states, keep the one producing maximum chain length for p and push the resulting state to the deque.
6If any chain reaches length >= k, d is feasible; otherwise infeasible. Use this result to move binary-search boundaries.

Example Walkthrough

Input: side = 5, points = [[0,1],[0,4],[2,5],[5,3],[4,0]], k = 3

1.Clockwise order becomes: [0,1] -> [0,4] -> [2,5] -> [5,3] -> [4,0].
2.Try d = 4. Start with chain length 1 at first point.
3.As we scan, whenever current point is at least 4 away from candidate chain end, we can extend that chain.
4.Suppose chain reaches length 3 at some point; then d=4 is feasible.
5.Binary search continues to test larger distances until the maximum feasible d is found.

Output: Maximum feasible minimum distance (problem output).

Common Pitfalls

•Do not skip perimeter ordering; random point order breaks the DP transition logic.
•Feasibility check must be monotonic-safe for binary search: return true only when a full chain of size k exists.
•Use Manhattan distance exactly (|x1-x2| + |y1-y2|), not Euclidean distance.

3464.cs

public class Solution
{
    // Approach: Perimeter ordering + binary search on answer + deque-based feasibility DP.
    // Time: O(m log m + m log side) Space: O(m), where m = points.Length.
    public int MaxDistance(int side, int[][] points, int k)
    {
        var ordered = GetOrderedPoints(side, points);
        int l = 0;
        int r = side;

        while (l < r)
        {
            int m = (l + r + 1) / 2;
            if (IsValidDistance(ordered, k, m))
                l = m;
            else
                r = m - 1;
        }

        return l;
    }

    private record Sequence(int StartX, int StartY, int EndX, int EndY, int Length);

    // Returns true if we can select `k` points such that the minimum Manhattan
    // distance between any two consecutive chosen points is at least `d`.
    private bool IsValidDistance(List<int[]> ordered, int k, int d)
    {
        var dq = new LinkedList<Sequence>();
        dq.AddFirst(new Sequence(
            ordered[0][0], ordered[0][1], ordered[0][0], ordered[0][1], 1));
        int maxLength = 1;

        for (int i = 1; i < ordered.Count; ++i)
        {
            int x = ordered[i][0];
            int y = ordered[i][1];
            int startX = x;
            int startY = y;
            int length = 1;

            while (dq.Count > 0 &&
                   (Math.Abs(x - dq.First.Value.EndX) + Math.Abs(y - dq.First.Value.EndY) >= d))
            {
                var first = dq.First.Value;
                if (Math.Abs(x - first.StartX) + Math.Abs(y - first.StartY) >= d &&
                    first.Length + 1 >= length)
                {
                    startX = first.StartX;
                    startY = first.StartY;
                    length = first.Length + 1;
                    maxLength = Math.Max(maxLength, length);
                }
                dq.RemoveFirst();
            }
            dq.AddLast(new Sequence(startX, startY, x, y, length));
        }

        return maxLength >= k;
    }

    // Returns the ordered points on the perimeter of a square of side length
    // `side`, starting from left, top, right, and bottom boundaries.
    private List<int[]> GetOrderedPoints(int side, int[][] points)
    {
        var left = new List<int[]>();
        var top = new List<int[]>();
        var right = new List<int[]>();
        var bottom = new List<int[]>();

        foreach (var point in points)
        {
            int x = point[0];
            int y = point[1];
            if (x == 0 && y > 0)
                left.Add(point);
            else if (x > 0 && y == side)
                top.Add(point);
            else if (x == side && y < side)
                right.Add(point);
            else
                bottom.Add(point);
        }

        left.Sort((a, b) => a[1].CompareTo(b[1]));
        top.Sort((a, b) => a[0].CompareTo(b[0]));
        right.Sort((a, b) => b[1].CompareTo(a[1]));
        bottom.Sort((a, b) => b[0].CompareTo(a[0]));

        var ordered = new List<int[]>();
        ordered.AddRange(left);
        ordered.AddRange(top);
        ordered.AddRange(right);
        ordered.AddRange(bottom);
        return ordered;
    }
}

Was this solution helpful?