Evaluate Division

Medium#399graph

You get equations of the form x / y = k between variables, and queries x / y. Answer each query from the equations, or with -1 if they say nothing about it (a variable no equation names, or two variables no chain of equations links). Our equations: p / r = 5, r / u = 0.5, r / s = 4; queries: p / s, s / p, p / q. The answers are [20, 0.05, -1].

399 Evaluate DivisionWalkthrough · 1×

Example: the equations p / r = 5, r / u = 0.5, r / s = 4; find p / s, s / p and p / q.

p / r = 5, r / u = 0.5, r / s = 4prsuqueriesp/ss/pp/qanswers—dfs callstop on the right—
not visitedon the path, waitingcurrent callend, the variable to reachreturned node / end, ↑ beside itdead end, returned -1

graph = empty map: for each variable, its arrows

01/68
restart · back · play · step
Speed
1function calcEquation(equations, values, queries):
2 graph = empty map // variable → its (next, weight)
3 for each equation x / y = k:
4 graph[x].add((y, k))
5 graph[y].add((x, 1 / k))
6 answers = []
7 for each query start / end:
8 if start not in graph or end not in graph:
9 answers.add(-1)
10 else:
11 answers.add(dfs(start, end, empty set))
12 return answers
13
14function dfs(node, end, visited):
15 if node == end:
16 return 1
17 visited.add(node)
18 for (next, weight) in graph[node]:
19 if next not in visited:
20 rest = dfs(next, end, visited)
21 if rest != -1:
22 return weight * rest
23 return -1
state
start
–
end
–
node
–
next
–
weight
–
rest
–
visited
–
answers
–
click a step to go back

← → step · space play/pause

Why it works

  1. An arrow x → y with weight k says x / y = k, and the arrow back says y / x = 1 / k. Along a path the fractions chain: (p / r) × (r / s) = p / s, so the product of the weights is the answer.
  2. Depth-first search tries one arrow at a time; a branch that cannot reach the end, like u here, returns -1, and the walk goes on with the next arrow. visited keeps it from going round in circles.
  3. Only a variable that some equation names is in the graph, so a query about any other one is -1 straight away.

Complexity

Time O(q × (n + m)), where n is the number of variables, m the number of equations and q the number of queries: each query is one walk that visits a variable at most once. Memory O(n + m) for the graph and visited.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.