# Java 3ms Floyd-Warshall-like transitive closure

• The idea behind transitive closure is to pre-calculate the fully connected components (as much as we can - as there might be disconnected graph parts), so that we can get to constant time query evaluation. Getting to transitive closure in this case is just applying a modified Floyd-Warshall's all-pairs shortest path algorithm to calculate the first found two pairs connecting the third pair - we do not want minimization as ideally division is going to be deterministic. This is O(n^3) time and O(n^2) space.

``````public class Solution {

public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
if (queries.length == 0) return new double[0];

List<String> vars = new ArrayList<String>();

for (int i = 0; i < equations.length; i++) {
String a = equations[i][0];
String b = equations[i][1];
}

double[][] mx = new double[vars.size()][vars.size()];

for (int i = 0; i < vars.size(); i++) {
mx[i][i] = 1;
}

for (int i = 0; i < equations.length; i++) {
int a = vars.indexOf(equations[i][0]);
int b = vars.indexOf(equations[i][1]);
mx[a][b] = values[i];
mx[b][a] = 1/values[i];
}

for (int i = 0; i < mx.length; i++) {
for (int j = 0; j < mx.length; j++) {
if (mx[j][i] == 0) continue;
for (int k = 0; k < mx.length; k++) {
if (mx[j][k] != 0) continue;
if (mx[i][k] != 0) {
mx[j][k] = mx[i][k] * mx[j][i];
mx[k][j] = 1/mx[j][k];
continue;
}
}
}
}

int q = 0;
double[] result = new double[queries.length];
for (String[] query: queries) {
int a = vars.indexOf(query[0]);
int b = vars.indexOf(query[1]);
if (a == -1 || b == -1) {
result[q++] = -1;
continue;
}

result[q++] = mx[a][b] == 0 ? -1 : mx[a][b];
}
return result;
}
}
``````

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