# Modular Java solution using graph

• The idea is to precompute all the distances in advance and then evaluate each query in constant time. Since with a valid input the graph is actually a tree (or a graph where all paths from node a to node b have the same distance), we can compute all the distances in O(N^2) and not in O(N^3) as in Floyd-Warshall.

``````public class Solution {
public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
// Precompute all distances in O(N^2), where N is the number of distinct variables
Map<String, Map<String, Double>> eqMap = computeDistances(equations, values);
double[] result = new double[queries.length];

// Compute each query in O(1) time using the precomputed distances
for (int i = 0; i < queries.length; ++i) {
if (eqMap.containsKey(queries[i][0])) {
result[i] = eqMap.get(queries[i][0]).getOrDefault(queries[i][1], -1.0);
} else {
result[i] = -1.0;
}
}

return result;
}

// Compute all the possible distances and store them in a map
private Map<String, Map<String, Double>> computeDistances(String[][] equations, double[] values) {
// Use eqMap to store the graph
Map<String, Map<String, Double>> eqMap = new HashMap<>();
// Use completeMap to store the graph + all the inferred distances
Map<String, Map<String, Double>> completeMap = new HashMap<>();
for (int i = 0; i < equations.length; ++i) {
}

// Perform a DFS for each variable
Set<String> visited = new HashSet<>();
for (String start : eqMap.keySet()) {
computeDistances(eqMap, start, start, 1.0, visited, completeMap);
visited.clear();
}
return completeMap;
}

// Depth first search implementation
private void computeDistances(Map<String, Map<String, Double>> eqMap, String start, String current, Double prev,
Set<String> visited, Map<String, Map<String, Double>> completeMap) {
for (Map.Entry<String, Double> nbr : eqMap.get(current).entrySet()) {
computeDistances(eqMap, start, nbr.getKey(), prev * nbr.getValue(), visited, completeMap);
}
}
}

// Helper method to add a distance and its reverse
private void addVal(Map<String, Map<String, Double>> eqMap, String left, String right, Double val) {
if (!eqMap.containsKey(left)) {
eqMap.put(left, new HashMap<>());
}
if (!eqMap.containsKey(right)) {
eqMap.put(right, new HashMap<>());
}

eqMap.get(left).put(right, val);
eqMap.get(right).put(left, 1.0 / val);
}
}
``````

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