Min Cost to Connect All Points

1public int minCostConnectPoints(int[][] points) {
2    int n = points.length;
3    if (n <= 1) return 0;
4
5    // Build all edges
6    List<int[]> edges = new ArrayList<>();
7    for (int i = 0; i < n; i++) {
8        for (int j = i + 1; j < n; j++) {
9            int cost = Math.abs(points[i][0] - points[j][0]) +
10                       Math.abs(points[i][1] - points[j][1]);
11            edges.add(new int[]{cost, i, j});
12        }
13    }
14
15    // Sort by cost
16    edges.sort((a, b) -> a[0] - b[0]);
17
18    // Union-Find
19    int[] parent = new int[n];
20    int[] rank = new int[n];
21    for (int i = 0; i < n; i++) parent[i] = i;
22
23    // Kruskal's algorithm
24    int totalCost = 0, edgesUsed = 0;
25
26    for (int[] edge : edges) {
27        if (edgesUsed == n - 1) break;
28        int cost = edge[0], u = edge[1], v = edge[2];
29
30        int pu = find(parent, u), pv = find(parent, v);
31        if (pu != pv) {
32            union(parent, rank, pu, pv);
33            totalCost += cost;
34            edgesUsed++;
35        }
36    }
37
38    return totalCost;
39}
40
41private int find(int[] parent, int x) {
42    if (parent[x] != x) parent[x] = find(parent, parent[x]);
43    return parent[x];
44}
45
46private void union(int[] parent, int[] rank, int x, int y) {
47    if (rank[x] < rank[y]) { int t = x; x = y; y = t; }
48    parent[y] = x;
49    if (rank[x] == rank[y]) rank[x]++;
50}