A campus fiber team is given building coordinates and one number: the cheapest cable that still links every building. Distance is Manhattan. The intern generated every set of n - 1 pairs and checked which ones connected all sites. Five buildings in staging returned before standup. A hundred in production were still choosing combinations when the request timed out. They switched to Dijkstra from building 0. The shortest-path tree looked fully linked. It was not the cheapest.
Min Cost to Connect All Points asks for the minimum total Manhattan cost to connect every point — the MST of the complete graph on those coordinates. A graph of all pairs already gives every legal edge for free. Trying every spanning tree uses that and still pays a combination count.
This is an interview writeup, not a layout lecture. That post owns adjacency list versus matrix. Kruskal owns sort-and-union. Union-find owns path compression and rank. Prim with a min-heap of crossing edges is the sibling — Java’s PriorityQueue, default order, not reverseOrder(). Do not paste that walk unless they ask. Here we only emit every pair as a weighted edge, sort, and skip a pair whose endpoints already share a root.
The problem
Given int[][] points where points[i] = [xi, yi], return the minimum cost to connect all points. The cost of connecting i and j is the Manhattan distance |xi - xj| + |yi - yj|. Points are connected when there is a path between every pair. You may add an edge between any pair — the graph is complete and implicit.
points = [[0,0],[2,2],[3,10],[5,2],[7,0]] → 20
points = [[3,12],[-2,5],[-4,1]] → 18
points = [[0,0],[1,1],[1,0],[-1,1]] → 4
points = [[0,0]] → 0First row: four tree edges of costs 3, 4, 4, 9. Second: three points, edges 6 and 12. Third: a cheap 4-cycle; the tree drops the expensive diagonal. Fourth: one point is already connected.
Note: Manhattan, not Euclidean. |Δx| + |Δy|. A shortest-path tree from one source is a different object — that is Network Delay Time, and it is not this MST.
Trying every spanning tree is the honest brute force
Build every unordered pair as an edge. Choose every subset of exactly n - 1 edges. Keep a subset only when those edges connect all n points — an undirected tree — and track the minimum total cost. Correct. Combinatorial.
int minCostConnectPointsBrute(int[][] points) {
int n = points.length;
if (n <= 1) {
return 0;
}
List<int[]> edges = new ArrayList<>();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int cost = Math.abs(points[i][0] - points[j][0])
+ Math.abs(points[i][1] - points[j][1]);
edges.add(new int[] { cost, i, j });
}
}
int[] best = { Integer.MAX_VALUE };
choose(edges, 0, new ArrayList<>(), n, best);
return best[0];
}
void choose(List<int[]> edges, int i, List<int[]> picked, int n, int[] best) {
if (picked.size() == n - 1) {
if (connects(picked, n)) {
int sum = 0;
for (int[] e : picked) {
sum += e[0];
}
best[0] = Math.min(best[0], sum);
}
return;
}
if (i == edges.size() || picked.size() + (edges.size() - i) < n - 1) {
return;
}
picked.add(edges.get(i));
choose(edges, i + 1, picked, n, best);
picked.remove(picked.size() - 1);
choose(edges, i + 1, picked, n, best);
}
boolean connects(List<int[]> picked, int n) {
List<List<Integer>> adj = new ArrayList<>();
for (int k = 0; k < n; k++) {
adj.add(new ArrayList<>());
}
for (int[] e : picked) {
adj.get(e[1]).add(e[2]);
adj.get(e[2]).add(e[1]);
}
boolean[] seen = new boolean[n];
ArrayDeque<Integer> q = new ArrayDeque<>();
q.add(0);
seen[0] = true;
int vis = 0;
while (!q.isEmpty()) {
int u = q.poll();
vis++;
for (int v : adj.get(u)) {
if (!seen[v]) {
seen[v] = true;
q.add(v);
}
}
}
return vis == n;
}At n = 5 there are ten pairs and C(10, 4) = 210 candidate trees — a rounding error. At n in the hundreds you paid a combination search for a question Kruskal answers by sorting that same pair list once: what is the cheapest unused pair whose endpoints are still in different components?
Sort every Manhattan pair, skip same component
Emit every i < j as (cost, i, j) with cost = |Δx| + |Δy|. Sort by cost. Each point starts as its own root. Walk the sorted list. If find(i) and find(j) differ, hang one root under the other and add the cost; if they already match, that pair would close a cycle — skip it. Stop after n - 1 unions. Flatten-on-find and rank live in the union-find post; do not re-lecture them at this board unless they ask.
Walk the five-point campus. Points 0=(0,0), 1=(2,2), 2=(3,10), 3=(5,2), 4=(7,0).
sorted:
1—3 3
0—1 4
3—4 4
0—3 7
0—4 7
1—4 7
1—2 9
2—3 10
0—2 13
2—4 14
parent 0 1 2 3 4 spent 0 used 0
1—3 3 union spent 3 used 1
0—1 4 union spent 7 used 2
3—4 4 union spent 11 used 3
0—3 7 same root, skip
0—4 7 skip
1—4 7 skip
1—2 9 union spent 20 used 4 stop (n-1)The skipped 7s would have closed a cycle among 0, 1, 3, 4. Point 2 still needed a link; 1—2 at 9 is the cheapest that reaches it. The Java is that walk; union returns whether a merge happened so the used count can rise.
int minCostConnectPoints(int[][] points) {
int n = points.length;
List<int[]> edges = new ArrayList<>();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int cost = Math.abs(points[i][0] - points[j][0])
+ Math.abs(points[i][1] - points[j][1]);
edges.add(new int[] { cost, i, j });
}
}
edges.sort(Comparator.comparingInt(e -> e[0]));
int[] parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
int spent = 0;
int used = 0;
for (int[] e : edges) {
if (union(parent, e[1], e[2])) {
spent += e[0];
used++;
if (used == n - 1) {
break;
}
}
}
return spent;
}
int find(int[] parent, int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
return parent[x];
}
boolean union(int[] parent, int a, int b) {
int ra = find(parent, a);
int rb = find(parent, b);
if (ra == rb) {
return false;
}
parent[ra] = rb;
return true;
}Time is O(n² log n) — Θ(n²) pairs, sort dominates, each union is nearly constant. Space is O(n²) for the edge list plus O(n) for parent (and the find call stack). n = 1 never enters the loop and returns 0.
Note: Same-root skip is the Redundant Connection move — there that edge is the answer; here you skip it and keep adding until n - 1 unions. java.util.Stack is the wrong type. A FIFO ArrayDeque is BFS. Prim’s sibling frontier is a min-heap.
What interviewers usually poke next
- Prim. Grow from any seed with a
PriorityQueueof crossing edges(cost, point)— Java’s default order, notreverseOrder(). Same MST, different growth. Do not paste that walk here unless they ask; name the heap and stop. - Redundant Connection. Union until
find(a) == find(b); that edge would close a cycle. Same skip, different question: there you return the edge, here you ignore it. - Network Delay Time. That is a shortest-path tree from one source. Dijkstra from point
0does not build this MST — a cheap spoke that is slightly longer from the source can still belong in the global tree. - Euclidean, or another metric. Still Kruskal (or Prim) if you change only the cost formula. Say so; do not re-derive MST.
n = 1, or two points. One point is cost0. Two points is a single Manhattan edge. The complete graph onnpoints hasn(n - 1)/2edges; you only keepn - 1of them.
You are done with this problem when you can say, out loud, why enumerating spanning trees is correct and combinatorial, why Kruskal skips a pair that already shares a root, and why a shortest-path tree from one point is not that MST.