Problem Statement in English

You’re given a square of side length side and an array points where points[i] = [x, y] is the coordinate of the i-th point on the perimeter of the square. You are also given an integer k.

You have to find the maximum distance between any two points on the perimeter of the square such that there are at least k points on the perimeter of the square that are at least that distance apart.

Return the maximum distance.

Approach

To make calculating the distance easier, we unroll the square into a linear array. We can do this by iterating through the points and calculating their distance from the starting point (0, 0) in a clockwise manner.

So for points on the:

  • Bottom edge: distance = x
  • Right edge: distance = side + y
  • Top edge: distance = 2 * side + (side - x)
  • Left edge: distance = 3 * side + (side - y)

Now we need to find the maximum distance d such that there are at least k points that are at least d apart. But the question is what is our starting point?

Our starting point needs to be such that we’re able select atleast k - 1 points after it, and the distance between all each pair of points is atleast d. So this means the first point and the last point we select should be atleast d apart.

Since we need the points to be in order, we should sort the linear array.

Thus our starting point needs to be early as possible and will also be before points[0] + d.

To figure out the actual points we select, we can use binary search to find the next point that is atleast d apart from the last point we selected.

We can use binary search to find the maximum d that satisfies the above condition.

And we’re done!

Solution in Python


class Solution:
    def maxDistance(self, side: int, points: List[List[int]], k: int) -> int:
        linear = []
        for x, y in points:
            if y == 0:          # Bottom
                linear.append(x)
            elif x == side:     # Right
                linear.append(side + y)
            elif y == side:     # Top
                linear.append(2 * side + (side - x))
            else:               # Left
                linear.append(3 * side + (side - y))
        
        linear.sort()
        n = len(linear)
        perimeter = 4 * side

        def check(dist):
            for i in range(n):
                if linear[i] > linear[0] + dist: break
                
                count = 1
                last_pos = linear[i]
                start_pos = linear[i]
                
                curr = i
                for _ in range(k - 1):
                    target = last_pos + dist
                    idx = bisect_left(linear, target)
                    
                    if idx < n:
                        last_pos = linear[idx]
                        count += 1
                    else:
                        break
                
                if count == k and (perimeter - (last_pos - start_pos)) >= dist:
                    return True
            return False

        low, high = 0, side
        ans = 0
        
        while low <= high:
            mid = (low + high) // 2
            if mid == 0: 
                low = 1
                continue
            if check(mid):
                ans = mid
                low = mid + 1
            else:
                high = mid - 1
        return ans

Complexity

  • Time: $O(n \log n)$
    Since we sort the array and for each distance we check, we iterate through the points and do a binary search.

  • Space: $O(n)$
    Since we store the linear array.

Mistakes I Made

I had to look this up :(

And we are done.