Connect all points with minimum total Manhattan distance cost (MST problem).
Input: points=[[0,0],[2,2],[3,10],[5,2],[7,0]] → Output: 20
Input: points=[[3,12],[-2,5],[-4,1]] → Output: 18
Prim's algorithm: greedily add the closest unvisited point to the MST.
- Use min-heap of (cost, point_index)
- Start with point 0, cost 0
- While not all points visited: pop min cost point
- Add to MST, add all edges to unvisited points to heap
- Return total cost
public int minCostConnectPoints(int[][] points) {
int n = points.length;
boolean[] visited = new boolean[n];
PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->a[0]-b[0]);
pq.offer(new int[]{0, 0});
int cost = 0, count = 0;
while (count < n) {
int[] cur = pq.poll();
if (visited[cur[1]]) continue;
visited[cur[1]] = true;
cost += cur[0];
count++;
for (int j = 0; j < n; j++) {
if (!visited[j]) {
int d = Math.abs(points[cur[1]][0]-points[j][0]) + Math.abs(points[cur[1]][1]-points[j][1]);
pq.offer(new int[]{d, j});
}
}
}
return cost;
}
- Time Complexity: O(n^2 log n)
- Space Complexity: O(n^2)