Min Cost to Connect All Points: Prim's MST on a Point Cloud
The Prim's MST solution to Min Cost to Connect All Points — Manhattan-distance edges, a worked walkthrough, JavaScript code, and O(V²) complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
You have a scatter of points on a grid, and you want to wire them all together with the least possible cable. Any two points can be connected, and the cost of a wire is their Manhattan distance. What's the cheapest set of wires that leaves every point reachable from every other?
That prompt is a Minimum Spanning Tree problem wearing a geometry costume. The moment you see "connect everything for the least total cost," the answer is one of the two classic MST algorithms — and because every pair of points is connectable, the graph is complete, which quietly picks the algorithm for you: Prim's.
The problem
Given an array points of 2D integer coordinates, the cost of connecting points[i] and points[j] is the Manhattan distance |xi − xj| + |yi − yj|. Return the minimum total cost to connect all the points so that there is exactly one simple path between any two of them.
Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output: 20The optimal wiring uses these four edges: 0–1 (cost 4), 1–3 (cost 3), 3–4 (cost 4), and 1–2 (cost 9), summing to 20. Two facts fall out of the statement:
- With
npoints you always spend exactlyn − 1edges — a tree has no cycles and no redundant wires. - Every pair is a candidate edge, so the graph is complete:
npoints hiden(n−1)/2possible connections.
The brute force baseline
The literal reading is: build every possible edge, sort them cheapest-first, and greedily add edges that don't form a cycle. That's Kruskal's algorithm with a union-find.
function minCostConnectPoints(points) {
const n = points.length;
const edges = [];
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
const dist = Math.abs(points[i][0] - points[j][0]) +
Math.abs(points[i][1] - points[j][1]);
edges.push([dist, i, j]);
}
}
edges.sort((a, b) => a[0] - b[0]);
// ...then run union-find, adding the cheapest edges that join two components.
}This is correct, but it materializes the entire edge list — n(n−1)/2 entries, which is O(V²) memory — and then sorts it in O(V² log V). For a complete graph, building and sorting all the edges just to keep n − 1 of them is wasteful. We can avoid ever holding the edge list.
The key insight: grow one tree, compute edges on demand
Prim's algorithm never builds an edge list. It grows a single tree from a seed node, and at each step it adds the cheapest edge that reaches a point not yet in the tree.
Why is a greedy pick safe? The cut property: if you split the points into "in the tree" and "not yet in the tree," the cheapest edge crossing that divide is guaranteed to belong to some MST. So repeatedly grabbing the cheapest outgoing edge can never paint you into a corner.
Because the graph is complete, we don't precompute distances — we compute the Manhattan distance from the point we just added to each remaining point, on the fly. A min-heap keeps the frontier of candidate edges ordered so the cheapest one is always one pop() away.
The optimal solution
This mirrors the visualizer's canonical implementation exactly — a heap-driven Prim's that pushes [distance, node] pairs and pops the cheapest frontier edge each round.
var minCostConnectPoints = function(points) {
let n = points.length;
let pq = new MinPriorityQueue(x => x[0]);
let minCost = 0;
let visited = new Array(n).fill(false);
pq.push([0, 0]);
let edgesUsed = 0;
while (edgesUsed < n) {
let [nodeDist, node] = pq.pop();
if (visited[node]) continue;
visited[node] = true;
minCost += nodeDist;
edgesUsed++;
for (let nextNode = 0; nextNode < n; ++nextNode) {
if (!visited[nextNode]) {
let nextDist =
Math.abs(points[node][0] - points[nextNode][0]) +
Math.abs(points[node][1] - points[nextNode][1]);
pq.push([nextDist, nextNode]);
}
}
}
return minCost;
};Three details carry the whole algorithm. The heap orders by x[0], the distance, so pop() always returns the cheapest pending edge. The if (visited[node]) continue line is lazy deletion: a node can sit in the heap under several stale distances, but we only "spend" it the first time it surfaces, and skip every later copy. And edgesUsed counts nodes locked into the tree; once all n are in, every point is connected and minCost is the answer.
Walkthrough
Trace points = [[0,0],[0,5],[5,0],[5,5]] — four corners of a square. The pairwise Manhattan distances are d(0,1)=5, d(0,2)=5, d(0,3)=10, d(1,2)=10, d(1,3)=5, d(2,3)=5. We seed the heap with [0, 0].
Pop [dist, node] | Already visited? | minCost | edgesUsed | Pushed to pq |
|---|---|---|---|---|
| (seed) | — | 0 | 0 | [0,0] |
[0,0] | no | 0 | 1 | [5,1] [5,2] [10,3] |
[5,1] | no | 5 | 2 | [10,2] [5,3] |
[5,2] | no | 10 | 3 | [5,3] |
[5,3] | no | 15 | 4 | — |
After the fourth pop, edgesUsed === 4 === n, so the loop exits and we return 15 (three edges: 0–1, 0–2, and one of the 5-cost wires into corner 3).
Notice the heap still holds a stale [10,3] and a duplicate [5,3] when we stop. If the loop had reached them, visited[3] would already be true, so continue would discard them without touching minCost. That's lazy deletion doing its job — we never had to remove entries from the heap eagerly.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Build all edges + Kruskal | O(V² log V) | O(V²) | materialize ~V²/2 edges, then sort them |
| Prim's + binary heap (this solution) | O(V² log V) | O(V²) | each of V nodes pushes up to V edges; every pop is O(log V²) |
| Prim's + minDist array | O(V²) | O(V) | scan V candidate distances V times, no heap at all |
For a complete graph, the heap doesn't help asymptotically — the edge count is already V², so pushing them all dominates. The tightest solution replaces the heap with a plain minDist[] array (the state the visualizer animates): each round, linearly scan for the cheapest unvisited point, then relax its neighbors. That drops space to O(V) and time to a clean O(V²) with no log factor.
Common mistakes
- Forgetting the graph is complete. There's no adjacency list to read — every pair is an edge, and you compute distances on demand. New solvers waste time looking for edges that were never given.
- Using Euclidean distance. The cost is Manhattan (
|Δx| + |Δy|), not√(Δx² + Δy²). Squaring and rooting silently produces wrong totals. - Skipping the lazy-deletion check. Drop
if (visited[node]) continueand a node gets counted multiple times, inflatingminCost. The heap holds stale entries by design; you must reject them on pop. - Off-by-one on the stopping condition. You need
nnodes in the tree (equivalentlyn − 1edges). Seeding with[0, 0]and looping whileedgesUsed < nis what makes the counts line up — the seed's zero-cost pop is node 0 joining for free. - Reaching for Kruskal by reflex. It works, but on a dense graph it materializes and sorts V² edges. Prim's with an array stays O(V²) and never allocates the edge list.
Where this pattern shows up next
Greedy graph frontiers and union-find both branch off from here:
- Redundant Connection — the union-find half of MST reasoning, used to spot the one edge that closes a cycle.
- Network Delay Time — Dijkstra runs the same heap-driven "pop the cheapest frontier, relax neighbors" loop, but sums path costs instead of edge costs.
- Course Schedule II — a different tree-vs-cycle question, resolved with topological order instead of a spanning tree.
- Shortest Path in Binary Matrix — the unweighted cousin, where a BFS frontier replaces the priority queue.
You can also step through the algorithm interactively to watch the tree grow point by point and the Manhattan distances update in real time.
FAQ
Should I use Prim's or Kruskal's for Min Cost to Connect All Points?
Prim's is the better fit. Because every pair of points is connectable, the graph is complete with V² edges, and Prim's with a minDist array runs in O(V²) time and O(V) space without ever building the edge list. Kruskal's needs all V² edges materialized and sorted, costing O(V² log V) time and O(V²) space. Both give a correct MST, but Prim's matches the shape of this problem — dense graph, distances computed on demand.
Why Manhattan distance instead of Euclidean?
The problem defines the cost of a wire as |xi − xj| + |yi − yj|, the Manhattan (grid) distance. Substituting the straight-line Euclidean distance changes every edge weight and can change which spanning tree is minimal, so it produces wrong answers. Manhattan distance also stays in integer arithmetic, which avoids floating-point comparison headaches inside the heap.
What is the time and space complexity?
The heap-based version shown here is O(V² log V) time and O(V²) space, because each of the V nodes pushes up to V candidate edges and each heap operation is logarithmic. The tighter refinement — Prim's with a linear minDist array — is O(V²) time and O(V) space, which is optimal for a complete graph since you must at least look at every pair of points once.
Why does the heap store [dist, node] and skip visited nodes?
The heap is a frontier of candidate edges, each recorded as [distance, targetNode] and ordered by distance so pop() yields the cheapest reachable point. A single node can be pushed several times under different distances as the tree grows, so many of those entries go stale. The if (visited[node]) continue guard is lazy deletion: the first time a node surfaces it joins the tree, and every later stale copy is discarded on pop without affecting the total cost.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.