Problem statement

https://binarysearch.com/problems/Shortest-Distance-Between-Two-Points/

Solution

The idea is to use divide and conquer idea, where we sort points by x coordinate and then separate them into two halves. Then we as for answers in both parts and consider possible strip of points in the middle.

Complexity

Complexity of given code is O(n*log^2 n), however it can be made O(n log n) as well. In fact given constrains and fast python sort function, it works almost the same (if not faster) than true O(n log n) solution.

Code

class Solution:
    def solve(self, P):
        def D(P1, P2):
            return (P1[1] - P2[1])**2 + (P1[0] - P2[0])**2

        def dist_BF(beg, end):
            ans = float("inf")
            for i in range(beg, end+1):
                for j in range(i+1, end + 1):
                    ans = min(ans, D(P[i], P[j]))
            return ans

        def dist(beg, end):
            if end - beg <= 3:
                return dist_BF(beg, end)
            
            mid = (beg + end)//2
            dist1 = dist(beg, mid)
            dist2 = dist(mid+1, end)
            dist_min = min(dist1, dist2)
            strip = []
            line = (P[mid][0] + P[mid+1][0]) / 2

            for i in range(beg, end+1):
                if (line - P[i][0])**2 <= dist_min:
                    strip += [P[i]]

            strip.sort(key = lambda x: (x[1], x[0]))
            for i in range(len(strip)):
                for j in range(i + 1, len(strip)):
                    if strip[j][1] - strip[i][1] >= dist_min: break
                    dist_min = min(dist_min, D(strip[i], strip[j]))

            return dist_min

        P = sorted(P)
        return dist(0, len(P) - 1)