BinarySearch 0980 Point Distances with Shared Coordinate

Problem statement

https://binarysearch.com/problems/Point-Distances-with-Shared-Coordinate/

Solution

Keep dictionary for every x keep coordinates of y and visa verse. Also use binary search.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def solve(self, P):
        dx, dy = defaultdict(list), defaultdict(list)
        for x, y in P:
            dx[x] += [y]
            dy[y] += [x]

        for x in dx: dx[x] = sorted(dx[x])
        for y in dy: dy[y] = sorted(dy[y])
        ans = []
        
        for x, y in P:
            dist = float("inf")
            idx1 = bisect.bisect_left(dx[x], y)
            if idx1 > 0: dist = min(dist, y - dx[x][idx1 - 1])
            if idx1 + 1 < len(dx[x]): dist = min(dist, dx[x][idx1 + 1] - y)
            idx2 = bisect.bisect_left(dy[y], x)
            if idx2 > 0: dist = min(dist, x - dy[y][idx2 - 1])
            if idx2 + 1 < len(dy[y]): dist = min(dist, dy[y][idx2 + 1] - x)
            ans += [dist]

        return ans