O(nlog(side)) with easy to understand proof
ApproachSolve for minimum perimeter distance instead of minimum Manhattan distance. Remap the 2D points to 1D points along a circular array at  positions [0, pe
# Approach

Solve for minimum perimeter distance instead of minimum Manhattan distance. Remap the 2D points to 1D points along a circular array at  positions `[0, perimeter)`. Sort the points. We will binary search over the minimum distance allowed, which we will call `gap`. We must write a checker function to see if we can select >= `k` points for a given `gap` size. To do this, we will use a deque to store 'streaks' in the form of `(start point, end point, length)`. Sweep the points from left to right, adding a new streak `(x, x, 1)` when we pass through point `x`, and extending this streak as `(x, p, old_length+1)` whenever we reach a point `p` that is far enough away from its current end point. The time complexity of this checker function is `O(nk)`, but we can reduce it to `O(n)` by observing that some streaks can be discarded, due to being worse than others.

Specific details of the algorithm and proof of correctness is provided below.

# Proof

To begin, notice that we can solve for minimum perimeter distance instead of minimum Manhattan distance. This is because perimeter distance can only be inconsistent with Manhattan distance when looking at two points on opposing sides of the square. In such cases, the actual (Manhattan) distance is >= `side`, and perimeter distance can overestimate. However, because `len(points) >= 4`, there must exist an adjacent pair of points that are <= `side` away from each other along the perimeter. In such case, perimeter distance is true to Manhattan distance. Thus, it doesn't matter that perimeter distance can overestimate for some pair distances, because it cannot possibly affect the result.

To calculate perimeter distance, we will flatten the points onto a 1D circular array within the range `[0, perimeter)`.

We will binary search over the minimum distance allowed. This takes `O(log(side))` steps. We need to write a checker function to test if we can select >= `k` points with a minimum distance allowed of `gap`.

The standard way to solve this problem is to select a point, then repeatedly accept the earliest next right point that is atleast `gap` distance away, until we have made a full loop around the circular array. If we do this for every point, then we will solve the problem. However, it turns out it is sufficient to stop accepting points once we have reached the origin `0`. Why is this? Lets rephrase what we would be doing. We would be calculating the maximum number of points we could select ***for each leftmost point***. The selection with the maximum number of points overall has a leftmost point ***somewhere***, therefore we will cover it.

Now, to implement the solution, we will use a deque that stores streaks in the form of `(start, end, length)`. We will sweep through the points from left to right (aka. `0` to `perimeter`). When we pass by a point `x`, we will insert it into the deque as a length 1 streak `(x, x, 1)`. When we pass by a point `p` that is far enough away, such that it can be used to extend this streak, we will pop this streak and push an extended streak of `(x, p, old_length+1)`. This will produce the maximum length streak for all starting points. This would have time complexity of `O(nk)`, because we can just short-circuit when we found any streak that has grown to length `k`.

However, we can reduce the time complexity to `O(n)`, by observing that we 1. do not need to start a new streak for current point `p`, if we are able to use it to extend an pre-existing streak & 2. only need to extend one streak, if we are able to extend several.

Lets explain why this is the case. First, we should recognize that if two streaks `s` and `t` are both extended with point `p`, then all the points that they will accept from that point onwards will be the same, EXCEPT potentially for when we reach the ***head meets tail zone*** of `(perimeter-gap, perimeter)`. At this zone, `s` might be able to accept an additional point that `t` cannot, if `s` has a later starting point than `t`. Vice versa is also true. Therefore, the rule for choosing between two streaks of equal length is obvious: pick the streak that has the later starting point. Now, for streaks of differing length, we just need to observe that the min and max number of points we can select in the ***head meets tail zone*** of `(perimeter-gap, perimeter)` is 0 and 1, respectively. This means that the difference in length between two extended streaks `s` and `t` could change by at most 1, when we consider the points in this zone. This means that longer streaks are ***always at least as good*** as shorter streaks. So we will always prefer to extend the longer streak. Lastly, we always prefer to extend rather than create a new streak, because that is equivalent to comparing extension of two streaks with differing length (`1+` vs. `0`).

The time complexity of the improved checker is `O(n)`, because we only push at most `n` streaks into the deque, and we can only pop as many as we can push.

Overall time complexity is `O(nlog(side))`. Space complexity is `O(n)`. There could be an `O(nlogn)` factor in the time complexity due to sorting the points, but you could also substitute STL sort with radix sort, which is `O(nlog(side))`.

Hope this helps!



# Code
```python3 []
class Solution:
    def maxDistance(self, side: int, points: List[List[int]], k: int) -> int:
        n = len(points)
        perimeter = side*4

        # flatten to 1D array
        # map x <= y to [-2*side, 0]
        # map x > y to (0, 2*side)
        # then shift right by 2*side to map to [0, perimeter)
        shift = 2*side
        a = []
        for x,y in points:
            ABS = abs(x) + abs(y)
            p = -ABS if x <= y else ABS
            a.append(p + shift)


        # O(nlog(side))
        # aside: optimal choice of b could be found by minimizing log_b(4*side) * (n + c*2**b)
        def radix_sort(a, b=8):
            
            maxb = perimeter.bit_length()
            mask = (1<<b)-1
            sh = 0
            
            while sh < maxb:
                buckets = [[] for _ in range(2**b)]
                for x in a:
                    buckets[x>>sh & mask].append(x)
                
                a = list(chain.from_iterable(buckets))
                sh += b
            
            return a
        
        a = radix_sort(a)
        # a.sort()
        

        def check(gap):

            # trivial case
            if k == 1:
                return True

            # [(start, end, length)]
            q = deque()

            for x in a:

                beststart = None
                bestlength = None

                while q and q[0][1] <= x - gap:
                    start, _, length = q.popleft()
                    
                    # x cannot be used to extend a streak if it is too close to its' start point
                    # but this would also imply that all subsequent points would be too close
                    # therefore, this streak is finished
                    if start + (perimeter - x) < gap:
                        continue
                    
                    # choose the best streak to extend
                    # longer streaks win
                    # tiebreak with later start point
                    if beststart is None or length > bestlength or (length == bestlength and start > beststart):
                        beststart = start
                        bestlength = length
                
                # extending a streak
                if beststart is not None:
                    newlength = bestlength + 1
                    if newlength >= k:
                        return True
                    q.append((beststart, x, newlength))
                # creating a new streak
                else:
                    q.append((x, x, 1))

            return False


        # binary search over minimum distance allowed
        lo = 1
        hi = perimeter//k

        # [lo, hi]
        while lo < hi:
            mid = (lo+hi+1)//2

            if check(mid):
                lo = mid
            else:
                hi = mid-1

        return lo


```
['Python3']