Build all edges (complete graph), then run Kruskal:
function minCostConnectPoints(points):
n = points.length
edges = []
for i from 0 to n-1:
for j from i+1 to n-1:
dist = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
edges.add((dist, i, j))
sort(edges)
uf = new UnionFind(n)
cost = 0
edgesUsed = 0
for each (dist, u, v) in edges:
if uf.union(u, v):
cost += dist
edgesUsed += 1
if edgesUsed == n - 1:
break
return cost
Time: . There are edges, sort.
For large , Prim's algorithm with a heap is faster on dense graphs.