Given points as (x,y) coordinates, connect all points using minimum total Manhattan distance. Each point connects to exactly one path (minimum spanning tree).
Input: [[0,0],[2,2],[3,10],[5,2],[7,0]] → Output: 20Input: [[3,12],[-2,5],[-4,1]] → Output: 18
Prim's MST algorithm: start from any node, greedily add the closest unvisited node.
- dist[] tracks minimum cost to include each node in MST.
- For each of n-1 steps: pick min-dist unvisited node u, mark visited.
- Update dist[v] for all unvisited v using Manhattan distance.
- Sum all picked distances.
class Solution {
public int minCostConnectPoints(int[][] points) {
int n = points.length;
int[] dist = new int[n];
boolean[] visited = new boolean[n];
java.util.Arrays.fill(dist, Integer.MAX_VALUE);
dist[0] = 0;
int total = 0;
for (int i = 0; i < n; i++) {
int u = -1;
for (int j = 0; j < n; j++) if (!visited[j] && (u == -1 || dist[j] < dist[u])) u = j;
visited[u] = true;
total += dist[u];
for (int v = 0; v < n; v++) {
if (!visited[v]) {
int d = Math.abs(points[u][0]-points[v][0]) + Math.abs(points[u][1]-points[v][1]);
dist[v] = Math.min(dist[v], d);
}
}
}
return total;
}
}
- Time Complexity: O(N^2)
- Space Complexity: O(N)