Leetcode 1584. How to make my Kruskal&Union Find algorithm faster?

Question

The question was on Leetcode 1584. Min Cost to Connect All Points. My answer to this question is:

class Solution {
    public int minCostConnectPoints(int[][] points) {
        List<int[]> list = new ArrayList<>();
        for(int i = 0; i < points.length; i++){
            for(int j = 0; j < points.length; j++){
                int dist = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);
                list.add(new int[]{i,j,dist});
            }
        }
        list.sort((int a[], int b[]) -> a[2] - b[2]);
        UnionFindSet uf = new UnionFindSet(points.length);
        int totalCost = 0;
        for(int edges[] : list){
            if(uf.Find(edges[0]) != uf.Find(edges[1])){
                uf.Union(edges[0],edges[1]);
                totalCost += edges[2];
            }
        }
        return totalCost;
    }
}

class UnionFindSet {
    public final int[] parents;

    UnionFindSet(int size) {
        this.parents = new int[size];
        for (int i = 0; i < size; i++) {
            this.parents[i] = i;
        }
    }

    public int Find(int x) {
        if (this.parents[x] != x) {
            this.parents[x] = Find(this.parents[x]);
        }
        return this.parents[x];
    }

    public void Union(int x, int y) {
        this.parents[Find(y)] = Find(x);
    }
}

My answer can pass all the test cases but the speed is extremely slow. Any idea how could I improve my code to make it faster? One of my guesses is maybe the nested for loop to calculate the Manhattan Distance is expensive, but I don't know how to omit or replace it. Any idea would be appreciated!

Answer 1

Your solution already seems to be implemented (rather) efficiently. My only advice is to rename Find and Union to find and union, respectively (Java style prefers lowercase chars at the first verb of a method name).

In UnionFindSet, you have

public final int[] parents;

I suggest you hide it by the private keyword instead of public.

In case you, in fact, seek for greater efficiency, take a look a this Wikipedia article. Perhaps it makes sense to implement all the discussed implementations of the disjoint set data structure and benchmark them all in order to find the fastest version.