Min Cost to Connect All Points

Intuition

Connecting all points with the smallest total cost and exactly one path between any pair is precisely a Minimum Spanning Tree. Because any two points can be linked directly, the underlying graph is complete, so we can materialize all n*(n-1)/2 candidate edges. Kruskal's algorithm sorts these edges by weight and walks them from cheapest to most expensive. An edge is accepted only when its endpoints currently sit in different components, which a union-find structure checks in near-constant time. Once we have accepted n-1 edges, every point is joined and the accumulated weight is the answer.

Algorithm walkthrough

1. 1Initialize a union-find over the n points, each point its own component.
2. 2For every pair (i, j) build an edge whose weight is the Manhattan distance between points i and j.
3. 3Sort all edges in non-decreasing order of weight.
4. 4Scan the sorted edges; for each, find the roots of both endpoints.
5. 5If the roots differ, union them, add the weight to the running total, and count the edge.
6. 6Stop as soon as n-1 edges have been accepted and return the total cost.

Implementation

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        n = len(points)
        parent = list(range(n))

        def find(x: int) -> int:
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        edges = []
        for i in range(n):
            for j in range(i + 1, n):
                dist = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
                edges.append((dist, i, j))

        edges.sort()
        total = 0
        used = 0
        for dist, i, j in edges:
            ri, rj = find(i), find(j)
            if ri != rj:
                parent[ri] = rj
                total += dist
                used += 1
                if used == n - 1:
                    break
        return total