Modular Java solution using graph


  • 0
    I

    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) {
                addVal(eqMap, equations[i][0], equations[i][1], values[i]);
                addVal(completeMap, equations[i][0], equations[i][1], values[i]);
            }
            
            // Perform a DFS for each variable
            Set<String> visited = new HashSet<>();
            for (String start : eqMap.keySet()) {
                visited.add(start);
                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) {
            addVal(completeMap, start, current, prev);
            for (Map.Entry<String, Double> nbr : eqMap.get(current).entrySet()) {
                if (visited.add(nbr.getKey())) {
                    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);
        }
    }
    

Log in to reply
 

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