Graphs - DFS· 25 min

Evaluate Division

LeetCode #399 · Medium · Solution walkthrough with Java and Python code

Graphs - DFS · Medium

LeetCode 399: Evaluate Division — solution

Solve LeetCode 399 by modelling each equation a / b = k as weighted edges a → b (k) and b → a (1/k), then answering each query with a BFS that multiplies weights along the path — O(q · (V + E)) time.

Problem in plain words

You receive facts like a / b = 2.0, where each side is a variable name. Then you receive questions like a / c = ?. Answer each question using only the given facts; if the answer cannot be determined (an unknown variable, or no chain of facts connects the two), return -1.0. The facts never contradict each other and no division by zero happens.

Example: facts x / y = 4 and y / z = 0.5. Then x / z = 4 × 0.5 = 2, z / y = 2, x / x = 1, and x / w = -1 because w never appears.

Intuition

Draw a graph: each variable is a node, and a / b = k becomes an edge a → b with weight k plus an edge b → a with weight 1 / k. Multiplying ratios along a path chains them: (a / b) · (b / c) = a / c. So a query a / c is answered by finding any path from a to c and multiplying the weights on it. A BFS that carries the running product does exactly that.

Approach

  1. Build a hash map from each variable to a list of (neighbour, weight) pairs, adding both directions per equation.
  2. For each query (src, dst): if either variable is not in the graph, answer -1.0.
  3. Otherwise BFS from src with product 1.0, marking visited nodes.
  4. When you pop dst, its product is the answer. If the BFS finishes without reaching dst, answer -1.0.

Dry run

Edges: x → y (4), y → x (0.25), y → z (0.5), z → y (2). Query x / z:

PopProductPush
x1y with 1 × 4 = 4
y4z with 4 × 0.5 = 2
z2target reached → 2.0

Java solution

java
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);
            String b = equations.get(i).get(1);
            graph.computeIfAbsent(a, x -> new HashMap<>()).put(b, values[i]);
            graph.computeIfAbsent(b, x -> new HashMap<>()).put(a, 1.0 / values[i]);
        }
        double[] answers = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            answers[i] = solve(graph, queries.get(i).get(0), queries.get(i).get(1));
        }
        return answers;
    }

    private double solve(Map<String, Map<String, Double>> graph, String src, String dst) {
        if (!graph.containsKey(src) || !graph.containsKey(dst)) {
            return -1.0;
        }
        Deque<String> nodes = new ArrayDeque<>();
        Deque<Double> products = new ArrayDeque<>();
        Set<String> visited = new HashSet<>();
        nodes.offer(src);
        products.offer(1.0);
        visited.add(src);
        while (!nodes.isEmpty()) {
            String node = nodes.poll();
            double product = products.poll();
            if (node.equals(dst)) {
                return product;
            }
            for (Map.Entry<String, Double> edge : graph.get(node).entrySet()) {
                if (visited.add(edge.getKey())) {
                    nodes.offer(edge.getKey());
                    products.offer(product * edge.getValue());
                }
            }
        }
        return -1.0;
    }
}

Python solution

python
class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float],
                     queries: List[List[str]]) -> List[float]:
        graph = defaultdict(list)
        for (a, b), k in zip(equations, values):
            graph[a].append((b, k))
            graph[b].append((a, 1.0 / k))

        def solve(src, dst):
            if src not in graph or dst not in graph:
                return -1.0
            visited = {src}
            queue = deque([(src, 1.0)])
            while queue:
                node, product = queue.popleft()
                if node == dst:
                    return product
                for nxt, w in graph[node]:
                    if nxt not in visited:
                        visited.add(nxt)
                        queue.append((nxt, product * w))
            return -1.0

        return [solve(a, b) for a, b in queries]

Complexity

MeasureCostWhy
TimeO(q · (V + E))Each of the q queries may run a full BFS over V variables and E equations.
SpaceO(V + E)The graph, plus a visited set and queue per query.

Edge cases and common mistakes

  • `x / x` for a known variable — the BFS pops x immediately and returns 1.0.
  • `x / x` for an unknown variable — must be -1.0, not 1.0. Check graph membership first.
  • Forgetting the reverse edge — without b → a with weight 1 / k, queries in the opposite direction fail.
  • Variables in different components — the BFS exhausts without reaching dst, so return -1.0.
›Is there a faster approach for many queries?

Weighted Union-Find: each variable stores its ratio to its set's root. A query in the same set is ratio(a) / ratio(b); different sets give -1.0. Each query becomes nearly O(1).

›Why can any path be used?

The input is guaranteed consistent, so every path between two variables yields the same product. BFS just finds one of them.

46 / 75