Given points as (x,y) coordinates, find the minimum total Manhattan distance to connect all points (minimum spanning tree using Kruskal's).
Input: [[0,0],[2,2],[3,10],[5,2],[7,0]] → Output: 20Input: [[3,12],[-2,5],[-4,1]] → Output: 18
Generate all O(N^2) edges, sort by Manhattan distance, then use Kruskal's MST algorithm.
- Generate all edges (i,j,dist) for i
- Sort by distance.
- Union-Find: add edge if it connects two different components.
- Stop when n-1 edges are added.
import java.util.*;
class Solution {
int[] parent;
public 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++)
edges.add(new int[]{i,j,Math.abs(points[i][0]-points[j][0])+Math.abs(points[i][1]-points[j][1])});
edges.sort((a,b)->a[2]-b[2]);
parent = new int[n]; for (int i=0;i<n;i++) parent[i]=i;
int total=0, used=0;
for (int[] e : edges) {
if (used==n-1) break;
int pu=find(e[0]),pv=find(e[1]);
if (pu!=pv) { parent[pu]=pv; total+=e[2]; used++; }
}
return total;
}
private int find(int x){return parent[x]==x?x:(parent[x]=find(parent[x]));}
}
- Time Complexity: O(N^2 log N)
- Space Complexity: O(N^2)