Min Cost to Connect All Points

Generate every possible edge, sort by weight, and greedily add the cheapest edge that doesn’t create a cycle — checked with a union-find (disjoint set) structure. Stop once n - 1 edges have been added.

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]]  # path compression
                x = parent[x]
            return x

        def union(a: int, b: int) -> bool:
            ra, rb = find(a), find(b)
            if ra == rb:
                return False
            parent[ra] = rb
            return True

        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, count = 0, 0
        for dist, u, v in edges:
            if union(u, v):
                total += dist
                count += 1
                if count == n - 1:
                    break
        return total

Watch the plane: node fill tracks the union-find component, an amber edge is the one being considered, emerald edges stay in the MST, and a rose edge is a cycle being rejected.

Union-find trace for points = [[0,0],[2,2],[3,10],[5,2],[7,0]] (indices 0-4). Sorted edges by Manhattan distance: (1,3)=3, (0,1)=4, (3,4)=4, (0,3)=7, (0,4)=7, (1,4)=7, (1,2)=9, (2,3)=10, (0,2)=13, (2,4)=14. Processing in increasing order:

Four union operations (points 0,1,3,4 merge first, then 2 joins) connect all 5 points with total cost 3 + 4 + 4 + 9 = 20, matching the expected output. The three skipped edges would have formed cycles within the already-connected {0,1,3,4} component.

Building and sorting O(n²) edges dominates: O(n² log n) time. Storing all pairwise edges costs O(n²) space — this is the weak point when n is large (up to 1000, so ~500,000 edges, which is fine, but it wastes work on far-apart pairs Prim’s never has to materialize).

Prim’s algorithm grows a single tree one node at a time: repeatedly add the cheapest edge connecting the tree to any point not yet in the tree. Because the graph is complete (every pair of points has an edge), we never need to materialize all O(n²) edges up front — instead track, for every point not yet in the tree, its current cheapest known connection cost (min_dist), and update it lazily as new points join.

import heapq

class Solution:
    def minCostConnectPoints(self, points: list[list[int]]) -> int:
        n = len(points)
        visited = [False] * n
        min_dist = [float('inf')] * n
        min_dist[0] = 0
        pq = [(0, 0)]  # (cost, point index)
        total = 0
        count = 0

        while pq and count < n:
            d, u = heapq.heappop(pq)
            if visited[u]:
                continue
            visited[u] = True
            total += d
            count += 1
            for v in range(n):
                if not visited[v]:
                    dist = abs(points[u][0] - points[v][0]) + abs(points[u][1] - points[v][1])
                    if dist < min_dist[v]:
                        min_dist[v] = dist
                        heapq.heappush(pq, (dist, v))
        return total

Watch the tree grow: emerald points are in the tree, the amber edge is the frontier edge just popped, and the small badges next to unvisited points show their current best connection cost (min_dist).

Trace on the same example, points = [[0,0],[2,2],[3,10],[5,2],[7,0]] (indices 0-4), starting the tree at point 0:

Total = 4 + 3 + 4 + 9 = 20, matching. Note this greedy tree-growth reaches the same total cost as Kruskal’s on this input (an MST’s total weight is unique even when the specific edges chosen can differ) — here they happen to coincide.

Why it’s correct: this is the standard MST cut property — for any partition of vertices into “in the tree” and “not yet,” the minimum-weight edge crossing that cut is safe to add, because any MST can be modified to include it without increasing total weight.

Complexity: each of the n iterations scans all n points to update min_dist, and each update may push onto the heap — O(n²) point scans plus O(n²) log n heap operations in the worst case, i.e. O(n² log n) time (this can be tightened to O(n²) with a plain array-based “find min unvisited” instead of a heap, since the graph is dense). Space is O(n) for min_dist, visited, and the heap — no need to store all O(n²) edges.