Evaluate Division
Evaluate Division is LeetCode 399 (Medium). You get equations[i] = [Aᵢ, Bᵢ] and values[i], which mean Aᵢ / Bᵢ = values[i]. For every query [Cⱼ, Dⱼ], return the value of Cⱼ / Dⱼ, or -1.0 if it cannot be worked out.
- Each variable is a short string of lowercase letters and digits.
- A variable that appears in no equation is undefined, so any query that uses it has no answer.
- The equations never contradict each other and every value is positive, so no division by zero can occur.
There are at most 20 equations and 20 queries, so running a fresh search for each query is cheap.
- 1 <= equations.length <= 20
- equations[i].length == 2
- 1 <= Ai.length, Bi.length <= 5
- values.length == equations.length
- 0.0 < values[i] <= 20.0
- 1 <= queries.length <= 20
- queries[i].length == 2
- 1 <= Cj.length, Dj.length <= 5
- Ai, Bi, Cj, Dj consist of lower case English letters and digits.
Intuition
Equations chain together: if a / b and b / c are known, then a / c = (a / b) × (b / c). So treat each variable as a node and each equation as two weighted arrows, a → b with weight w and b → a with weight 1 / w.
The ratio of any two variables is then the product of the weights along a path between them. The equations are consistent, so every path between the same two variables gives the same product. That means any search will do, with no need for a shortest path. If no path exists, the two variables sit in separate groups of equations and nothing links their values.
Any problem where facts compose by multiplying, such as exchange rates, unit conversions or gear ratios, turns into this weighted graph: walk a path and multiply the edge weights. If queries vastly outnumber facts, weighted union-find answers each one without a search.
Approach
Before reading on: given a / b = 2 and b / c = 3, work out c / a by hand. Which equations did you use, and in which direction did you read each one? Then decide what x / x should return when x appears in no equation.
Two ways to solve it
Build arrows both ways, then search from the numerator for each query, multiplying weights along the path.
- Short: one dictionary and one loop.
- Fits the limits: 20 queries on at most 40 variables.
The answer most interviewers expect.
Group connected variables under one root and store each variable's ratio to its root.
- Queries:
c / d = ratio[c] / ratio[d]when both share a root. - Watch out: the weight update during path compression and union is easy to get backwards.
The usual follow-up when queries vastly outnumber equations.
DFS wins here: the inputs are tiny, the code is short and there is no weight formula to get wrong. The steps, code and live demo follow the DFS, and the union-find code comes after the demo.
Store every equation in both directions
For a / b = w, set graph[a][b] = w and graph[b][a] = 1 / w. A query may read an equation backwards, as in b / a, and the reverse arrow is what lets the search travel that way.
Answer -1.0 for an undefined variable
If either variable of the query is missing from graph, return -1.0 at once. This includes x / x for an unknown x: the problem treats it as undefined, so the shortcut "anything divided by itself is 1" must not be applied.
Search from the numerator, carrying a ratio
Start a stack with (src, 1.0) and a seen set holding src. Pop a pair (node, ratio); if node is the target, return ratio. The ratio stored with a node is always src / node, so when the target comes off the stack it holds the answer.
Push each unseen neighbour with ratio × weight
For each arrow node → nxt with weight w, skip nxt if it is already seen. Otherwise mark it and push (nxt, ratio × w), because (src / node) × (node / nxt) = src / nxt. Marking on push keeps every variable on the stack at most once.
Return -1.0 when the stack runs out
An empty stack means every variable linked to src has been visited without meeting the target. The two variables are in separate groups of equations, so their ratio is unknown.
Evaluate Division solution in Python | C++ | Java
Weighted union-find
parent[x] points toward the root of x's group and weight[x] stores x / parent[x]. find flattens the path and multiplies the weights on the way, so afterwards weight[x] is x / root. Joining a / b = v hangs the root of a under the root of b with weight v × weight[b] / weight[a], which is exactly root(a) / root(b). A query then divides the two ratios to the shared root.
Common pitfalls
Storing each equation one way only
graph[a][b] = value
graph[a][b] = value graph[b][a] = 1.0 / value
With equations = [["a", "b"]], values = [2.0] and the query ["b", "a"], the search starts at b, finds no arrow out of it and returns -1.0. The right answer is 0.5.
Searching without a seen set
for nxt, weight in graph[node].items():
stack.append((nxt, product * weight))for nxt, weight in graph[node].items():
if nxt not in seen:
seen.add(nxt)
stack.append((nxt, product * weight))Every equation adds an arrow back, so each pair of variables forms a loop. For equations = [["a", "b"], ["c", "d"]] and the query ["a", "d"], the stack keeps refilling with a and b and never empties, so the search never ends.
Sharing one seen set across queries
seen = set()
def ratio(src, dst):
seen.add(src)def ratio(src, dst):
seen = {src}In the first example, the query a / c marks a, b and c. The next query b / a then finds every neighbour already seen and returns -1.0 instead of 0.5. Each search needs a fresh set.
Edge cases
a / a where a is in an equationThe first pop is a itself, which is the target, so the answer is the starting ratio 1.0.
Complexity
Evaluate Division FAQ
Why multiply along the path instead of adding?
Each arrow is a ratio, and ratios chain by multiplying: (a / b) × (b / c) = a / c, because the b cancels. Adding weights would suit a path whose cost is a sum, such as distance. To reuse a sum-based algorithm, take logarithms of the weights; a sum of logs is the log of the product.
Can BFS replace DFS here?
Yes. Replace the stack with a queue and nothing else changes. Because every path between two variables gives the same product, the order in which variables are explored does not affect the answer, only which path happens to be found first.