# Java, Union-Find & Ranking & Path Compression, most efficient algorithm

• I had this question in a G interview. Linking parents will give you O(logn) for find operation, however, using path compression, it becomes constant time.

``````class Solution {
class Node {
int rank;
Node parent;
double ratio;
String val;
public Node(String val) {
this.val = val;
}
}
class Result {
Node parent;
double ratio;
}
public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
HashMap<String, Node> map = new HashMap();

for (int i = 0; i < equations.length; i++) {
String s1 = equations[i][0];
String s2 = equations[i][1];

Node n1 = map.getOrDefault(s1, new Node(s1));
Node n2 = map.getOrDefault(s2, new Node(s2));
map.put(s1, n1);
map.put(s2, n2);

union(n1, n2, values[i]);

}

double[] ret = new double[queries.length];
for (int i = 0; i < queries.length; i++) {
Node n1 = map.get(queries[i][0]);
Node n2 = map.get(queries[i][1]);

if (n1 == null || n2 == null) {
ret[i] = -1;
continue;
}

Result n1res = findParentAndRatio(n1);
Result n2res = findParentAndRatio(n2);
if (n2res.parent != n1res.parent) {
ret[i] = -1;
} else {
ret[i] = (n1res.ratio) * (1/n2res.ratio);
}
}

return ret;
}

public void union(Node n1, Node n2, double val) {
if (n1.parent == null) {
n1.parent = n1;
n1.ratio = 1;
}
if (n2.parent == null) {
n2.parent = n2;
n2.ratio = 1;
}
Result n1res = findParentAndRatio(n1);
Result n2res = findParentAndRatio(n2);

if (n1res.parent == n2res.parent) {
return; // no need
}

if (n2res.parent.rank > n1res.parent.rank) {
Node temp = n2;
n2 = n1;
n1 = temp;
Result tempRes = n2res;
n2res = n1res;
n1res = tempRes;
val = 1/val;
}

n2.parent = n1res.parent;
n2.ratio = n1res.ratio * (1/val);
n1res.parent.rank++;
}

public Result findParentAndRatio(Node n) {
double ratio = 1;
Node cur = n;

while (cur != cur.parent) {
ratio *= cur.ratio;
cur = cur.parent;
}

Result res = new Result();

res.ratio = ratio;
res.parent = cur;

//path compresion
n.ratio = res.ratio;
n.parent = res.parent;
return res;
}
}

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.