399. Evaluate Division

/**

 * 399. Evaluate Division

 * You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi]

 * and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single

 * variable.

 * You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer

 * for Cj / Dj = ?.

 * Return the answers to all queries. If a single answer cannot be determined, return -1.0.

 * Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and

 * that there is no contradiction.

 * Below solution is via DFS. A faster solution would be via union find. in union find you can check whether numerator

 * and denom are in same set to find whether division possibility exists. and then you can find the divisor weight

 * relative to root for each of the numerator and denom. you divide the two weights to get num/denom.  

*/

See solution to the problem on github here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/google/medium/EvaluateDivisions.java

This is an interesting problem in that it translates solving division equations via graph. The approach described here is based on graph traversal. See at the bottom another approach using union find.

Algorithm is:

Create a graph

• Create nodes based on equation and link edges between them
• Edge weights in reverse are inverse of the weights in other direction (I,e if a/b = 2, b/a = ½)

Traverse the graph to solve the equations

• If a/b is 2 and b/c is 3 then a/c = a/b * b/c. Therefore, we can traverse the graph from starting node A to find the target node c in order to solve a/c while carrying the multiple of weights between the traversal nodes.
• So, in code traverseQuery we just run a dfs on nodes until we find the target. Once we find the target we return the multiple of weights across the edges traversed so far.
• To avoid repeated tarversals across same paths, we store the path weights in a memorization map to avoid recalculations.

Here is code to populate the tree data based on the equations passed in:

void populateNodeMap(List<List<String>> equations, double[] values) {
    int i = 0;
    for (List<String> equation : equations) {
        double val = values[i];
        String src = equation.get(0);
        String target = equation.get(1);
        Node nodeSrc = nodeMap.computeIfAbsent(src, l -> new Node(src));
        Node nodeDest = nodeMap.computeIfAbsent(target, l -> new Node(target));

        Edge edgeA = new Edge(val, nodeDest);
        nodeSrc.edges.add(edgeA);

        Edge edgeB = new Edge(1 / val, nodeSrc);
        nodeDest.edges.add(edgeB);

        i++;
    }
}

Here is code to solve the queries based on the graph created above:

double traverseQuery(Node node, String dest, Set<String> visited, String orig, double weight) {
    if (node == null) return -1;
    String searchPath = node.name + "," + dest;
    Double d = memorization.get(searchPath);
    if (d != null) {
        return d;
    }
    searchPath = orig + "," + node.name;
    memorization.put(searchPath, weight);
    visited.add(node.name);
    for (Edge edge : node.edges) {
        if (edge.dest.name.equals(dest)) {
            return edge.weight;
        }
        if (!visited.contains(edge.dest.name)) {
            searchPath = edge.dest.name + "," + dest;
            d = memorization.get(searchPath);
            if (d != null) {
                return d * edge.weight;
            }
            double val = traverseQuery(edge.dest, dest, visited, orig, weight * edge.weight);
            if (val != -1) {
                return val * edge.weight;
            }
        }
    }
    return -1;
}

A faster approach than above is to use union find for this problem. In union find, you can check whether numerator and denom are in same set to find whether division possibility exists. And then you can find the divisor and dividend weight relative to root for each of the numerator and denom. You divide the two weights to get the result.