> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/07-17-2022-1584.-min-cost-to-connect-all-points.md).

# 07/17/2022 1584. Min Cost to Connect All Points

Method: First we create an arrayList to contain the edgeList with the weight and index i and j.

Then in the nested for loop,  we calculate the distance between the index i and index i + 1, then input the distance, i ,j into the arraylist. Sort the edgeList in ascending order with the weight. Then use the Kruskal's algo the get the minimum spanning tree. Here we use disjoint set to help us to decide if the edge can be added to the MST. if union(index1, index2) is true, we add the weight to the result and if the edgesNum is same with points.length -1, we break and return the final result.

Time O(N^2 log(N)) There are n\* (n-1)/2 edges and we sort it. 

Space O(N^2)

```
// Some code
class UnionFind {
    private int[] root;
    private int[] rank;
    
    public UnionFind(int size) {
        this.root = new int[size];
        this.rank = new int[size];
        for (int i = 0; i < size; i++) {
            root[i] = i;
            rank[i] = 1;
        }
    }
    
    public int find(int x) {
        if (x == root[x])
            return x;
        return root[x] = find(root[x]);//path compression
    }
    
    public boolean union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        
        
        if (rootX == rootY) {
            return false;
        }
        
        if (rank[rootX] > rank[rootY]) {
            root[rootY] = rootX;
        } else if (rank[rootX] < rank[rootY]) {
            root[rootX] = rootY;
        } else {
            root[rootY] = rootX;
            rank[rootX] += 1;
        }
        
        return true;
    }
}
class Solution {
    public int minCostConnectPoints(int[][] points) {
        ArrayList<int[]> edgeList = new ArrayList<>();
        for (int i = 0; i < points.length - 1; i++) {
            for (int j = i + 1; j < points.length; j++) {
                int distance = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);
                int[] edge = {distance, i , j};
                edgeList.add(edge);
            }
        }
        
        Collections.sort(edgeList, (a,b) -> (a[0] - b[0]));
        
        UnionFind uf = new UnionFind(points.length);
        int minCost = 0;
        int edgeNum = 0;
        
        for (int[] edge: edgeList) {
            int weight = edge[0];
            int node1 = edge[1];
            int node2 = edge[2];
            if (uf.union(node1, node2)){
                minCost += weight;
                edgeNum++;
            }
            if (edgeNum == points.length - 1){
                break;
            }
        }
        return minCost;
    }
}
```