Min Cost to Connect All Points
Connect every point at the least total Manhattan distance with Prim's algorithm: a min-heap always attaches the cheapest new point to the tree.
Problem Understanding
Min Cost to Connect All Points: given points[i] = [x, y], connecting two points costs their Manhattan distance |x1 - x2| + |y1 - y2|. Return the minimum total cost so that every point is connected, meaning there is exactly one path between any two points.
Example: points = [[0,0],[2,2],[3,10],[5,2],[7,0]] returns 20.
The Intuition: Grow One Tree, Cheapest Edge First
Connecting all points with no cycles and the least total cost is a minimum spanning tree. Prim's algorithm grows it one point at a time:
- Start with point 0 alone in the tree.
- Of all edges from a tree point to a non-tree point, take the cheapest. That edge is always safe: any spanning tree must cross from "in" to "out" somewhere, and the cheapest crossing can never make it worse.
- Repeat until every point is in.
A min-heap holds the candidate edges, so the cheapest is one pop away. Each new point pushes its distance to every outside point; entries for points that joined in the meantime are stale and skipped. It is the same pop-cheapest-then-push loop as Network Delay Time's Dijkstra, except the key is the edge cost alone, not the distance from a source.
Interactive Walkthrough
Points are drawn at their coordinates. The tree grows in green; the heap of candidate edges is listed beside it, cheapest first. Try Stale entry to see an old, more expensive entry popped and skipped.
Dry Run Table
Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
| Pop (cost, point) | Action | Total |
|---|---|---|
| (0, 0) | start the tree at point 0 | 0 |
| (4, 1) | add 0 — 1 | 4 |
| (3, 3) | add 1 — 3 | 7 |
| (4, 4) | add 3 — 4 | 11 |
| three pops | points already in the tree: stale, skipped | 11 |
| (9, 2) | add 1 — 2 | 20 |
Answer: 20, using 4 edges for 5 points.
The Solution Template
Lazy Prim with a heap. JavaScript and TypeScript include a small binary heap. C uses the O(n²) array version of Prim, which keeps the cheapest known cost for each outside point instead of a heap.
Min Cost to Connect All Points Code
1var minCostConnectPoints = function(points) {2 const n = points.length, inTree = Array(n).fill(false);3 const heap = [[0, 0]];4 let total = 0, added = 0;5 while (added < n) {6 const [cost, u] = pop(heap);7 if (inTree[u]) continue;8 inTree[u] = true;9 total += cost;10 added++;11 for (let v = 0; v < n; v++) {12 if (!inTree[v]) {13 const d = Math.abs(points[u][0] - points[v][0]) + Math.abs(points[u][1] - points[v][1]);14 push(heap, [d, v]);15 }16 }17 }18 return total;19};2021// Minimal binary min-heap on [cost, point] pairs.22function push(heap, item) {23 heap.push(item);24 let i = heap.length - 1;25 while (i > 0) {26 const p = (i - 1) >> 1;27 if (heap[p][0] <= heap[i][0]) break;28 [heap[p], heap[i]] = [heap[i], heap[p]];29 i = p;30 }31}3233function pop(heap) {34 const top = heap[0], last = heap.pop();35 if (heap.length) {36 heap[0] = last;37 let i = 0;38 while (true) {39 let m = i;40 const l = 2 * i + 1, r = l + 1;41 if (l < heap.length && heap[l][0] < heap[m][0]) m = l;42 if (r < heap.length && heap[r][0] < heap[m][0]) m = r;43 if (m === i) break;44 [heap[m], heap[i]] = [heap[i], heap[m]];45 i = m;46 }47 }48 return top;49}
Edge Cases & Common Mistakes
- One point: nothing to connect; the answer is 0.
- Forgetting the in-tree check: a stale entry would add the same point twice and overcount the cost.
- Euclidean instead of Manhattan: the cost is
|dx| + |dy|, no square root. - Building all n² edges for Kruskal: works, but sorts about n²/2 edges; Prim avoids the full list.
- Ties: any cheapest edge is fine; different tie choices give different trees with the same total.
Summary
Treat the points as a complete graph with Manhattan weights and build a minimum spanning tree with Prim's algorithm: pop the cheapest attachment, skip it if stale, add the point and push its costs to every outside point. O(n² log n) time with a heap, or O(n²) with the array version.
More practice: DSA interview questions with answers · patterns cheat sheet