[Python][Beat 98%]Binary Search, Easy to understand Code with detailed comments
IntuitionFrom
https://leetcode.com/problems/maximize-the-distance-between-points-on-a-square/solutions/6461777/greedy-binary-search-clean-and-simple-to-understa
# Intuition
From
https://leetcode.com/problems/maximize-the-distance-between-points-on-a-square/solutions/6461777/greedy-binary-search-clean-and-simple-to-understand-code-c

- Instead of a 2d problem make this into a circular 1D problem. This only works because we are working in Manhattan distance(and not Euler distance, which would take the shortest distance between 2 points) I do that by mapping points in the anti-clockwise manner(starting from bottom bound).
- After that use binary search for minimum distance, and choose the last distance that works(that should give the maximize the minimum distance). 
- The checking happens by fixing a start value and find the next k-1 terms for it. Use binary search to find the next element by increasing by atleast min Dist for the next element. We should also make sure that clock-wise distance from the first element to the current element should also be less than minDist . Repeat this step for all elements at distance less than min distance from first point.
# Approach
<!-- Describe your approach to solving the problem. -->

# Complexity
- 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 []
class Solution:
    def maxDistance(self, side: int, points: List[List[int]], k: int) -> int:
        def to1d(point:List[int]):
            if point[1]==0: # bottom bound
                return point[0]
            elif point[0]==side: # right bound
                return side+point[1]
            elif point[1]==side: # top bound
                return 3*side-point[0]
            else: # left bound
                return 4*side-point[1]
        arr = list(map(to1d,points))
        arr.sort() # sorted in anti-clockwise manner, starting from bottom.

        # Approach: you select 1 element & then find the next k-1 with a gap of minDist
        # If there isnt atleast k-1 elements to try, give up
        # By binary search you get an optional element in anti-clockwise manner, but you also check
        # for distance in the clockwise manner(which should be <minDist)
        def check(minDist):
            n = len(arr)
            # starting arr[0], next element should be atleast minDist distance
            startOfSecond = bisect.bisect_left(arr, arr[0] + minDist)
            # Exactly one point i in the range 0 <= i < startOfSecond must be selected 
            # If there aren't enough points to select after, return False
            if n - startOfSecond < k - 1:
                return False
            for i in range(startOfSecond):
                count = 1
                curPt = arr[i] # i is the first point of the current chain selected
                for _ in range(k - 1):
                    j = bisect.bisect_left(arr, curPt + minDist)
                    # if there are no more
                    if j>=n:
                        break
                    distFromEnd = (4 * side - arr[j])
                    clockwiseDist =  distFromEnd + arr[i]
                    # if clockwise dist to first point is not minDist, we can't take it
                    if clockwiseDist < minDist:
                        break
                    curPt = arr[j]
                    count += 1
                if count == k:
                    return True
            return False  
            
        # binary search on max of minimum distance
        left,right,ans = 1,side,1 # max of min manhattan distance is side (4 corners)
        while left<=right:
            mid = (left+right)//2
            if check(mid):
                ans = mid
                left = mid+1
            else:
                right = mid-1
        return ans
```
['Python3']