Min Cost to Connect All Points
Medium Prim's MST (dense graph)
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Connect all points on a plane so that every point can reach every other, where an edge costs the Manhattan distance between its points. Return the minimum total cost.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: connect all points as cheaply as possible (Manhattan distance).
Why this works: that's a minimum spanning tree. Prim's grows the tree by always adding the closest outside point.
Example: [[0,0],[2,2],[3,10],[5,2],[7,0]]
add edges 4, 3, 4, 9 → total 20✦Hints open one at a time
↗Approach
Keep minDist[i] = cheapest edge from the tree to point i. Repeat n times: pick the closest point not yet in the tree, add its cost, and update minDist of the others using it.
</>Solution (Java)
import java.util.*;
class Solution {
public int minCostConnectPoints(int[][] points) {
int n = points.length, total = 0;
int[] minDist = new int[n];
Arrays.fill(minDist, Integer.MAX_VALUE);
boolean[] inTree = new boolean[n];
minDist[0] = 0;
for (int step = 0; step < n; step++) {
int u = -1;
for (int i = 0; i < n; i++)
if (!inTree[i] && (u == -1 || minDist[i] < minDist[u])) u = i; // closest outside point
inTree[u] = true;
total += minDist[u];
for (int v = 0; v < n; v++) {
if (inTree[v]) continue;
int d = Math.abs(points[u][0] - points[v][0]) + Math.abs(points[u][1] - points[v][1]);
if (d < minDist[v]) minDist[v] = d;
}
}
return total;
}
}!Common mistake
Building all n² edges and sorting them for Kruskal — works but uses much more memory.
- Time: O(n²).
- Space: O(n).