Evaluate Division
Evaluate Division: given equations like a / b = 2.0, answer queries such as a / c. Return -1.0 for any query that cannot be determined.
- 1 <= equations.length <= 20
- values.length == equations.length
- 1 <= queries.length <= 20
- 0.0 < values[i] <= 20.0
- Variables consist of lowercase English letters.
Intuition
Each equation is an edge between two variables carrying a ratio. a / b = 2 means an edge a → b weighted 2, and b → a weighted 1/2. A query is then a walk from one variable to the other, and the answer is the product of the weights along the way.
When relationships compose multiplicatively — ratios, exchange rates, unit conversions — model them as a weighted graph and multiply along the path. The tell is a transitive relation with an inverse. Union-Find with weights solves it too, and is preferable when queries vastly outnumber equations.
Approach
Before reading on: if a/b = 2 and b/c = 3, how do you get a/c, and what does that suggest about combining edges along a path? Then list every reason a query might be unanswerable.
Ratios compose along a path
If a / b = 2 and b / c = 3, then a / c = 2 × 3 = 6. Division chains multiply, which is exactly what makes a graph the right model: each edge contributes its weight and the path product is the answer. Store both directions when building — the forward edge with weight w and the reverse with 1/w — because a / b = w implies b / a = 1/w, and without the reverse edge many queries become unreachable.
Each query is a traversal accumulating a product
For query x / y, run a DFS or BFS from x carrying a running product that starts at 1. Multiply by each edge weight as you traverse, and when y is reached return the accumulated value. A visited set is essential: the graph contains cycles by construction, since every edge has a reverse, so an unguarded traversal loops forever. Any path gives the same answer when the equations are consistent, so the first one found can be returned immediately.
The three ways a query fails
Return -1.0 when either variable never appeared in the equations — an unknown symbol has no node at all — or when both exist but lie in different connected components, so no chain of ratios links them. The one case that must not fail is x / x for a known x, which is 1.0 by definition and is handled naturally since the traversal starts at the target. With V variables and Q queries, each traversal is O(V + E), giving O(Q · (V + E)).
Solution & live demo
Common pitfalls
Storing only the forward edge
graph[a][b] = value
graph[a][b] = value graph[b][a] = 1.0 / value
a / b = w also tells you b / a = 1/w. Without the reverse edge, queries that need to travel backwards along an equation report -1.0 even though the answer is known.
No visited set
stack.append((neighbour, product * weight))
if neighbour not in seen:
seen.add(neighbour)
stack.append(...)Every edge has a reverse, so the graph is full of two-node cycles. An unguarded traversal bounces between a and b forever.
Returning 1.0 for any self-division
if src == dst:
return 1.0if src not in graph or dst not in graph:
return -1.0x / x is 1.0 only when x actually appeared in the equations. For an unknown variable the answer is -1.0, so the existence check must come first.
Edge cases
The variable has no node, so the answer is -1.0 rather than 1.0.
The traversal begins at the target and returns the initial product of 1.0.
The traversal exhausts its component without reaching the target, giving -1.0.
Weights multiply along the path — 2.0 × 3.0 = 6.0.
The reverse edge stored as 1/w answers it directly.