Min Cost to Connect Points (MST)

Signal

"Connect everything at minimum total edge cost" — no cycles required, just full connectivity as cheaply as possible — is a Minimum Spanning Tree. The twist here: the graph isn't given explicitly, it's implicitly complete (every pair of points has an edge, weighted by Manhattan distance).

Approach

Grow the tree with Prim's algorithm: start from any point, and repeatedly add the cheapest edge that connects an already-visited point to an unvisited one, using a min-heap of (cost, point) candidates. Because the graph is dense (every pair is an edge), Prim's growing-frontier approach avoids ever materializing all O(n²) edges as an explicit list up front — you compute distances to remaining points on the fly.

Skeleton

visited = {0}, heap = [(dist(0, p), p) for p in other points]
total = 0
while fewer than n points visited:
    cost, p = heap.pop_min()
    if p in visited: continue
    visited.add(p); total += cost
    for q not in visited: heap.push((dist(p, q), q))
return total

Solution

import heapq

def min_cost_connect_points(points: list[list[int]]) -> int:
    n = len(points)
    visited = [False] * n
    min_heap = [(0, 0)]  # (cost, point index) — start at point 0 for free
    total = 0
    edges_used = 0

    while edges_used < n:
        cost, i = heapq.heappop(min_heap)
        if visited[i]:
            continue
        visited[i] = True
        total += cost
        edges_used += 1
        xi, yi = points[i]
        for j in range(n):
            if not visited[j]:
                xj, yj = points[j]
                dist = abs(xi - xj) + abs(yi - yj)
                heapq.heappush(min_heap, (dist, j))

    return total

Complexity

O(n² log n) time — for each of n points added to the tree, we may push up to n candidate edges onto the heap. O(n²) space in the worst case for the heap. Kruskal's + DSU on an explicitly sorted edge list is an O(n² log n) alternative that's preferable if the graph were sparse instead of complete.

Pitfalls

• Skipping the if visited[i]: continue check after popping — the heap can hold multiple stale entries for the same point at different costs; only the first (cheapest) pop for a given point should count.
• Building the full O(n²) edge list up front and sorting it (Kruskal's) also works but is heavier here than Prim's incremental approach, since the graph is dense and complete rather than sparse.
• Forgetting this is Manhattan distance (|dx| + |dy|), not Euclidean — mixing them silently gives a wrong-but-plausible-looking total cost.