Problem Statement

Minimum Cost to Connect All Points

You are given some points on a flat map. Your job is to lay down "roads" between points so every point is reachable from every other point, and you want to spend as little as possible. A road between two points costs the Manhattan distance between them: |xi - xj| + |yi - yj|. Manhattan distance just means you count horizontal steps plus vertical steps, like walking city blocks instead of cutting diagonally across. The cheapest way to connect everything without wasting any road is called a Minimum Spanning Tree, or MST. "Spanning" means it touches every point, "tree" means there are no extra loops, and "minimum" means the total cost is as small as it can be. To build it we will use a min-heap. A min-heap is like a magic bucket of options where the cheapest option always floats to the top, so you can grab the smallest one fast every time. That fits perfectly here, because at each step we want the cheapest road we haven't used yet.

mediumGraphMSTGraphsTime: O(n² log n) · Space: O(n)

Signals to notice

connect all points with minimum total wirecomplete graphMST on coordinates

Brute force first

Try all possible spanning trees — exponential. That direct path helps you understand the question, but it tends to treat every possibility as brand new instead of learning from earlier steps.

The key insight

Compute all pairwise Manhattan distances as edges. Apply Prim's (min-heap) or Kruskal's (sort + union-find). Prim's is better here since the graph is dense (complete). Instead of recomputing the world every time, you preserve just enough context to let the next decision become obvious.

Trace it on `points=[[3,12],[-2,5],[-4,1]]`

init: visited={}, heap=[(0,0)], total=0
pop(0,0): visit 0, total=0; push dists from pt0 -> (12,1),(18,2)
pop(12,1): visit 1, total=12; push dist from pt1 to 2 -> (6,2); heap=[(6,2),(18,2)]
pop(6,2): visit 2, total=18 (the (18,2) entry is now stale)
|visited|=3 == n, loop ends
return total = 18

What must stay true

The minimum cost to connect all points is the MST weight. Manhattan distance |x1-x2| + |y1-y2| is the edge weight between any two points. As long as that statement keeps holding, you can trust the steps built on top of it.

Shape of the loop

heap = [(0, start)]; visited = {}; total = 0
while |visited| < n:
    cost, i = pop_min(heap)
    if i in visited: continue
    visited.add(i); total += cost
    for j not in visited: push(heap, (manhattan(i, j), j))
return total

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Using Kruskal's on a complete graph — that's for sorting all edges. Prim's with a visited array avoids generating all edges upfront. The fix is usually to return to the meaning of each move, not just the steps themselves.

Graphs Pattern