Appearance
4.21.2 — Min Cost to Connect All Points
LeetCode 1584 · Medium
The problem
Given points on a plane, connect them all at minimum total cost, where the cost of joining two points is their Manhattan distance, |x_1 - x_2| + |y_1 - y_2|.
points = [[0,0],[2,2],[3,10],[5,2],[7,0]] → 20Up to 1,000 points.
The pattern
"Connect everything as cheaply as possible" is a minimum spanning tree. The result is a tree because any cycle would contain an edge you could delete while keeping everything connected — so the cheapest connected graph never has one.
The graph here is complete and implicit: every pair of points is joined by an edge, so there are n(n-1)/2 of them — about 500,000 for n = 1000. Nobody hands you an edge list; you compute a distance whenever you need one.
Two standard algorithms, and the choice between them is decided by that density.
Prim's algorithm
Grow one tree from a starting point. Repeatedly add the cheapest edge that connects the tree to a point outside it.
A min-heap holds the candidate edges — the frontier — and always gives the cheapest.
python
import heapq
class Solution:
def minCostConnectPoints(self, points: List[List[int]]) -> int:
n = len(points)
in_tree = [False] * n
heap = [(0, 0)] # (cost, point index) — start at point 0 for free
total = 0
used = 0
while used < n:
cost, i = heapq.heappop(heap)
if in_tree[i]:
continue # stale entry — already added by a cheaper edge
in_tree[i] = True
total += cost
used += 1
xi, yi = points[i]
for j in range(n):
if not in_tree[j]:
xj, yj = points[j]
heapq.heappush(heap, (abs(xi - xj) + abs(yi - yj), j))
return totalts
function minCostConnectPoints(points: number[][]): number {
const n = points.length;
const inTree = new Array(n).fill(false);
const heap = new MinHeap<[number, number]>((e) => e[0]);
heap.push([0, 0]);
let total = 0, used = 0;
while (used < n) {
const [cost, i] = heap.pop()!;
if (inTree[i]) continue;
inTree[i] = true;
total += cost;
used++;
const [xi, yi] = points[i];
for (let j = 0; j < n; j++) {
if (!inTree[j]) {
const [xj, yj] = points[j];
heap.push([Math.abs(xi - xj) + Math.abs(yi - yj), j]);
}
}
}
return total;
}The if in_tree[i]: continue is lazy deletion. A point may be pushed several times with different costs, once for each tree point that could reach it. Rather than finding and updating the old entry — which a heap cannot do efficiently — you leave the stale entries in and skip them when they surface. The cheapest copy always pops first, so the answer is correct.
Lazy deletion is the standard way to use a heap when priorities change, and it comes back in Dijkstra (4.21.3).
Starting with (0, 0) adds point 0 to the tree at no cost, which is right — you have to start somewhere and starting is free.
O(n^2 \log n) here, because each of the n additions pushes up to n edges.
Kruskal's algorithm
Sort all the edges by cost, then add each one whose endpoints are not already connected, using union-find. Stop after n − 1 successful unions.
python
class Solution:
def minCostConnectPoints(self, points: List[List[int]]) -> int:
n = len(points)
edges = []
for i in range(n):
for j in range(i + 1, n):
d = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
edges.append((d, i, j))
edges.sort()
parent = list(range(n))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
total, used = 0, 0
for d, i, j in edges:
ri, rj = find(i), find(j)
if ri == rj:
continue # already connected → would make a cycle
parent[rj] = ri
total += d
used += 1
if used == n - 1: # a spanning tree has exactly n−1 edges
break
return totalO(E \log E), and here E = n^2/2, so O(n^2 \log n) as well — but it must build and sort half a million edges, which costs real memory.
used == n - 1 is the stopping rule, and it is the n − 1 fact from 4.20.12.
Which to use
| Prim's | Kruskal's | |
|---|---|---|
| structure | heap of frontier edges | sorted edge list + union-find |
| dense graphs | better — never materialises all edges | must build and sort O(V^2) edges |
| sparse graphs | fine | often simpler |
| edges given explicitly | either | natural |
| edges implicit (like here) | natural | you must generate them all |
For this problem Prim's is the better answer, because the graph is complete and implicit. Kruskal's has to generate 500,000 edges just to sort them.
Say the trade in one sentence and the choice justifies itself.
Why greedy is correct
Both algorithms are greedy, and greedy is usually suspect — so it is worth knowing why it is safe here. The justification is the cut property:
Split the nodes into any two groups. The cheapest edge crossing that split is in some minimum spanning tree.
Prim's uses it directly: the split is tree versus not-tree, and the heap gives the cheapest crossing edge. Kruskal's uses it too: an edge joining two different components is the cheapest edge crossing the split between them, because everything cheaper has already been considered.
4.19.2 proves it properly. Being able to name the cut property is what separates "I know the algorithm" from "I know why it works" — and 4.25 is entirely about that distinction.
Complexity
O(n^2 \log n) time and O(n^2) space for the heap in the worst case. With n = 1000 that is comfortable.
A dense-graph variant of Prim's using an array instead of a heap runs in O(n^2) with O(n) space, which is actually better here — keep a min_cost[] array and scan it for the minimum each round. Worth mentioning as the optimisation for complete graphs.
Where this goes next
- Connecting Cities With Minimum Cost, Optimize Water Distribution — MST with an explicit edge list. The water problem has a lovely trick: a well in a village is modelled as an edge to a virtual node 0.
- Network delay, cheapest flights — shortest path, not MST. The distinction matters: MST minimises the total cost of connecting everything; shortest path minimises the cost from one source to each node. They are different problems and usually different trees.
- Real uses — network design, clustering (cut the k−1 most expensive MST edges to get k clusters), and circuit layout.
What the interviewer will push on
"MST or shortest path?" MST — the question is connecting everything cheaply, not travelling from a source.
"Prim's or Kruskal's, and why?" Dense implicit graph → Prim's. Give the edge-count figure.
"Why is the greedy choice safe?" The cut property.
"What are those stale heap entries?" Lazy deletion, because heaps cannot update a priority.
"When do you stop?" After n − 1 edges, because that is what a spanning tree has.
One thing to volunteer: state that MST and shortest path are different problems, and that the MST path between two nodes is generally not the shortest path between them. It is a common confusion and naming it is a strong signal.
Next: 4.21.3 Network Delay Time — the shortest-path problem, and Dijkstra.