Min Cost to Connect All Points

def minCostConnectPoints(points):
    n = len(points)
    dist = [float('inf')] * n   # cheapest link
    dist[0] = 0
    seen = [False] * n
    total = 0
    for _ in range(n):
        u = min((d, i) for i, d in enumerate(dist) if not seen[i])[1]
        seen[u] = True
        total += dist[u]
        x, y = points[u]
        for v, (a, b) in enumerate(points):
            if not seen[v]:
                dist[v] = min(dist[v], abs(x - a) + abs(y - b))
    return total

Min Cost to Connect All Points. Picture pins on a corkboard grid. Yarn between two pins follows the grid lines, so it costs the gap in x plus the gap in y. Connect every pin using the least yarn.

Take zero zero, two two, three ten, five two and seven zero. The cheapest network costs twenty. Three twelve, minus two five and minus four one cost eighteen.

Trying every spanning tree is hopeless: five pins have a hundred twenty-five, and ten pins have a hundred million. Tying each pin to its nearest neighbor is quick, but it can leave separate islands.

We want a minimum spanning tree, and Prim's algorithm grows one. Start at pin zero. Every pin outside remembers its cheapest link into the tree. Add the cheapest one, then let the rest check the new pin.

In code, a distance array holds each pin's cheapest link, starting at infinity. Each round, take the unseen pin with the smallest distance, add it to the total, and update the others.

From zero zero, two two costs four. Five two is then just three away. Seven zero is four from five two. Last, three ten joins two two for nine. Four, three, four and nine make twenty.

That's n rounds, each scanning n pins, so order n squared time, fine for a dense graph, and order n space. Kruskal's algorithm with union-find works too: sort the edges, then take the cheapest.

Grow, link, add. That's Min Cost to Connect All Points.