Evaluate Division LeetCode 399 Guide

LeetCode 399 Evaluate Division gives you a list of equations like ["a","b"] with corresponding values like 2.0, meaning a/b=2.0. You are then given queries like ["a","c"] and must return the computed value — or -1.0 if no path exists between those two variables.

The core challenge is chaining ratios: if a/b=2.0 and b/c=3.0, then a/c=6.0 by multiplying along the chain. Queries can ask about any pair, and if either variable never appeared in the equations, the answer must be -1.0. The problem guarantees no contradictions in the input.

This is a classic graph reachability problem with weighted edges. The variables form nodes, the equations form directed weighted edges, and each query is a path-finding problem where path value equals the product of edge weights along the route.

The insight that transforms this problem is recognizing each variable as a graph node and each equation as two directed weighted edges. For equation a/b=k, add edge a→b with weight k and edge b→a with weight 1/k. The reverse edge lets you traverse in both directions — computing b/a=0.5 from a/b=2.0.

A query [src, dst] then becomes: find any path from src to dst in the graph and multiply all edge weights along that path. If a/b=2 and b/c=3, the path a→b→c has edge weights 2 and 3, so a/c = 2*3 = 6. If no path exists, return -1.0.

This graph model cleanly handles all cases: self-division returns 1.0 (a node with a trivial path to itself), unknown variables return -1.0 (not in the graph), and multi-hop ratios are just weighted path products.

Use an adjacency list where each node maps to a list of (neighbor, weight) pairs. In Python, defaultdict(list) is ideal. In Java, use a HashMap<String, List<double[]>> where each double[] stores [neighborIndex, weight] or use a nested map.

Iterate through each equation [a, b] with value k. Add a → (b, k) and b → (a, 1.0/k) to the adjacency list. This bidirectional construction is what makes queries traversable in any direction. If the same variable appears multiple times across equations, it accumulates multiple neighbors.

After building the graph, collect the set of known variables. Any query variable not in this set immediately returns -1.0, avoiding unnecessary DFS calls into nonexistent nodes.

For each query [src, dst], perform a DFS from src accumulating the product of edge weights. Start with an accumulated value of 1.0. At each node, multiply the current accumulator by the edge weight before recursing to the neighbor.

Maintain a visited set to avoid cycles. If the current node equals dst, return the accumulated product — that is the answer for this query. If DFS exhausts all paths without reaching dst, return -1.0.

Handle edge cases before DFS: if src or dst is not in the graph, return -1.0 immediately. If src == dst and src is a known variable, return 1.0 without any traversal.

Weighted Union-Find is an elegant alternative where each node tracks its ratio relative to its root. The find(x) operation returns (root, ratio_to_root) — the root of x's component and the multiplier needed to reach the root from x.

When unioning two variables a and b with ratio k (a/b=k), first find both roots. If they share a root, do nothing. Otherwise, link the roots and set the weight such that the chain of ratios remains consistent. This requires careful weight adjustment during the union step.

To evaluate query a/c: call find(a) → (rootA, ratioA) and find(c) → (rootC, ratioC). If rootA != rootC, return -1.0 (different components). Otherwise return ratioA / ratioC — the ratio of both values relative to their shared root cancels out correctly.

The DFS version is simpler for interviews. In Python: build the graph with defaultdict(list), then for each query call a recursive dfs(node, dst, visited, acc) that returns acc when node==dst or -1.0 if stuck. Time complexity is O(Q * (V+E)) for Q queries over a graph with V nodes and E edges.

In Java, the structure mirrors Python: HashMap<String, List<double[]>> for the graph, a recursive dfs method returning double, and a HashSet<String> for visited tracking per query. Reset the visited set between queries. Space complexity is O(V+E) for the graph plus O(V) for the recursion stack.

Both approaches handle all edge cases cleanly by checking graph membership before any DFS. The overall space is O(V+E) where V is the number of unique variables and E is 2 * equations.length (bidirectional edges).

Network Delay Time (LC 743) and Cheapest Flights Within K Stops (LC 787) are canonical weighted graph problems where edge weights represent costs or delays rather than ratios. The difference with Evaluate Division is that path value is a product rather than a sum, but the graph traversal structure is identical.

Reconstruct Itinerary (LC 332) also uses a directed graph with edge traversal, though it focuses on Eulerian path construction rather than weighted path products. All three share the core insight: model the problem as a directed graph and use traversal algorithms to extract the answer.

The weighted Union-Find approach places Evaluate Division in the same family as problems like Accounts Merge and Redundant Connection — where Union-Find manages component connectivity, extended here to carry ratio metadata. Mastering both the DFS and Union-Find approaches gives you flexibility across the full weighted graph problem family.