238. Evaluate Division

Read each equation A / B = k as a pair of directed edges in a graph: an edge A → B with weight k, and B → A with weight 1/k. Then C / D is just the product of edge weights along any path from C to D — because the intermediate variables cancel in a telescoping chain. Finding that product is a depth-first search from C to D.

Model the equations as a graph

Each fact A / B = k tells us two things: A / B = k and B / A = 1/k. Represent variables as nodes and put a weighted directed edge for each direction: A → B weighted k, and B → A weighted 1/k.

Now consider a chain A / B = k1 and B / C = k2. Multiplying: A / C = (A/B) · (B/C) = k1 · k2. The B cancels. In graph terms, the value of A / C is the product of edge weights along a path A → B → C. This telescoping is the whole idea.

Answering a query C / D

1. If C or D never appeared in any equation, the answer is -1.0 — we know nothing about them.
2. If C == D (and C exists), the answer is 1.0.
3. Otherwise, run a DFS from C, carrying the running product of weights. When the search reaches D, that accumulated product is the answer. If no path reaches D, the variables are in disconnected components and the answer is -1.0.

We track a visited set to avoid cycling forever.

Algorithm

• Build: for each equations[i] = [a, b] with values[i] = v: graph[a][b] = v, graph[b][a] = 1/v.
• dfs(src, dst, visited): if src/dst unknown → -1; if src == dst → 1; mark src visited; for each neighbor nb with weight w, if a recursive dfs(nb, dst) returns a value ≠ -1, return w · that; if all fail, return -1.
• Answer each query with dfs(C, D, {}).

Worked example

Equations a/b = 2, b/c = 4. The graph has edges a→b (2), b→a (0.5), b→c (4), c→b (0.25).

• Query a/c: DFS from a → take a→b (×2) → from b take b→c (×4) → reached c. Product 2 · 4 = 8.
• Query b/a: b→a weight 0.5.
• Query a/e: e is unknown → -1.
• Query a/a: same node → 1.
• Query c/a: c→b (×0.25) → b→a (×0.5) → 0.125.

Result: [8, 0.5, -1, 1, 0.125].

Complexity

Let V be the number of distinct variables, E the number of equations, and Q the number of queries.

• Build: O(E).
• Each query: a DFS over the graph, O(V + E).
• Total: O(E + Q · (V + E)) time; O(V + E) space for the graph and recursion.

import java.util.*;

class Solution {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        Map<String, Map<String, Double>> graph = new HashMap<>();
        for (int i = 0; i < equations.size(); i++) {
            String a = equations.get(i).get(0), b = equations.get(i).get(1);
            double v = values[i];
            graph.computeIfAbsent(a, k -> new HashMap<>()).put(b, v);
            graph.computeIfAbsent(b, k -> new HashMap<>()).put(a, 1.0 / v);
        }
        double[] result = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            result[i] = dfs(graph, queries.get(i).get(0), queries.get(i).get(1), new HashSet<>());
        }
        return result;
    }

    private double dfs(Map<String, Map<String, Double>> graph, String src, String dst, Set<String> visited) {
        if (!graph.containsKey(src) || !graph.containsKey(dst)) return -1.0;
        if (src.equals(dst)) return 1.0;
        visited.add(src);
        for (Map.Entry<String, Double> e : graph.get(src).entrySet()) {
            if (visited.contains(e.getKey())) continue;
            double sub = dfs(graph, e.getKey(), dst, visited);
            if (sub != -1.0) return e.getValue() * sub;
        }
        return -1.0;
    }
}