Problem Statement in English

You’re given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [x_i, y_i].

Your task is to connect all the points in such a way that there is only one path between any 2 points, and the cost the path is minimized.

Approach

This is a classic problem of finding the minimum spanning tree. We can use Prim’s or Kruskal’s algorithm to solve this problem.

I’ve gone ahead and implemented Prim’s algorithm.

Solution in Python


class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        def manDist(x1, y1, x2, y2):
            return abs(x2 - x1) + abs(y2 - y1)

        l = len(points)
        res = 0
        used = 0

        curr = (points[0][0], points[0][1])

        minheap = []
        seen = set([curr])

        for x2, y2 in points:
            heappush(minheap, (manDist(curr[0], curr[1], x2, y2), x2, y2))

        while minheap:
            d, x, y = heappop(minheap)
            t = (x, y)

            if t in seen:
                continue

            res += d
            seen.add(t)
            used += 1

            if used == l - 1:
                return res

            for x2, y2 in points:
                if (x2, y2) not in seen:
                    heappush(minheap, (manDist(x, y, x2, y2), x2, y2))

        return res

Complexity

  • Time: O(nlogn)O(nlogn)
    Since we pop from the heap nn times and each pop operation takes O(logn)O(logn) time.

  • Space: O(n)O(n)
    Since we store at most nn elements in the heap and nn elements in the set.

And we are done.