CODEWITHSUNDEEP
javaalgorithmminimum-spanning-treekruskals-algorithmunion-find
Tangcb
Tangcb

Reputation: 11

Leetcode 1584. How can I improve my Kruskal&Union Find algorithm to make it faster?

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!

Upvotes: 1

Views: 224

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59174

Your UnionFindSet needs path compression and union by size or rank. They are explained pretty well in the wikipedia article: https://en.wikipedia.org/wiki/Disjoint-set_data_structure

They are also not hard to implement. I put an implementation in python over here: How to properly implement disjoint set data structure for finding spanning forests in Python?

Upvotes: 1

Related Questions