This medium LC problem is basically a minimum spanning tree problem therefore we can use Kruskal’s algorithm to solve it.

Kruskal’s algorithm relies on Union-Find datastructure to build connected components which will help us the minimum spanning tree.

Time complexity: O(nlogn) Space complexity: O(n), n = number of nodes

class Solution {
class DisjointSet {

private Map<Integer, Node> mapping = new HashMap<>();

class Node {
int rank;
int data;
Node parent;
}

public void makeSet(int n){
Node node = new Node();
node.rank = 0;
node.data = n;
node.parent = node;
mapping.put(n, node);
}

public void union(int x, int y){
if(mapping.containsKey(x) && mapping.containsKey(y)){
Node xNode = mapping.get(x);
Node yNode = mapping.get(y);

Node xSet = findSet(xNode);
Node ySet = findSet(yNode);

if(xSet == ySet) return;

// union by rank
if(xSet.rank >= ySet.rank){
xSet.rank = xSet.rank == ySet.rank ? xSet.rank + 1 : xSet.rank;
ySet.parent = xSet;
}else{
xSet.parent = ySet;
}
}
}

public int findSet(int data){
return findSet(mapping.get(data)).data;
}

public Node findSet(Node node){
Node parent = node.parent;
if(node == parent) return node;

// path compression
node.parent = findSet(node.parent);
return node.parent;
}
}

public int minimumCost(int N, int[][] connections) {
// use kruskal's algorithm

// sort the edges' weights in increasing order

Arrays.sort(connections, (a, b) -> a - b);

// create the disjoint set
DisjointSet ds = new DisjointSet();
for(int i=1 ; i <= N; i++){
ds.makeSet(i);
}

int result = 0;

// build the connected components
for(int[] connection : connections){
int a = ds.findSet(connection);
int b = ds.findSet(connection);

// if they are not on the same set, add the weight
if(a != b){
result += connection;

// then union them
ds.union(a, b);
}
}

// check if there's only 1 big connected component
int root = ds.findSet(1);
for(int i=2 ; i <= N; i++){
if(root != ds.findSet(i)) return -1;
}

return result;
}
}


Runtime: 33 ms, faster than 42.61% of Java online submissions for Connecting Cities With Minimum Cost. Memory Usage: 50.1 MB, less than 100.00% of Java online submissions for Connecting Cities With Minimum Cost.