Parametrizing binary search
IntuitionApproachThe key thing to note for this problem is that when the points all lie on the boundary of a square, the arrangement that maximizes the minimum
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->
The key thing to note for this problem is that when the points all lie on the boundary of a square, the arrangement that maximizes the minimum perimeter spacing also ends up maximizing the minimum Manhattan distance.

So, we can simply parametrize all values representing their distance along the perimeter. Additionally, we need to add all the values again but this, time, adding the perimeter to them. Why do we do this? Well, say we want to start at the last value in points. We need to check values that come after it, so by adding all the values again we are able to do so.

This solution was based on someone else's approach but I couldn't find them

# Complexity
We assume n is the length of points.
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
$$O(n log(n))$$

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ --> 
$$O(n)$$

# Code
```python3 []
import bisect

class Solution:
    def maxDistance(self, side: int, points: List[List[int]], k: int) -> int:
        arr = []
        P = 4*side
        n = len(points)
        #populate arr with our params
        for x, y in points:
            if y == 0:
                t = x
            elif x == side:
                t = side + y
            elif y == side:
                t = 3*side - x
            else:
                t = 4*side - y
            arr.append(t)
        arr.sort()
        arr2 = arr + [t + P for t in arr]
        def works(d):
            for i in range(n):
                count = 1
                curr = i
                last = arr2[i]
                valid = True
                for j in range(1, k):
                    #we want to find the smallest point, that is greater than arr but is at least distance d + last
                    index = bisect.bisect_left(arr2, last + d, curr + 1)
                    if index == len(arr2) or arr2[index] >= arr2[i] + P:
                        valid = False
                        break
                    count += 1
                    curr = index
                    last = arr2[index]
                    #if valid and count == k and (arr2[i] + P - last) >= d:
                    #this ensures that is we wrap around, our last point is still distance d away
                if valid and count == k and (arr2[i] + P - last) >= d:
                    return True
            return False


        low, high = 0, 2*side
        res = 0
        while low <= high:
            mid = (low + high) // 2
            if works(mid):
                low = mid + 1
                res = mid
            else:
                high = mid - 1
        return res


```
['Python3']