TL;DR
Model variables as a weighted graph and multiply edge weights along a path — DFS/BFS per query in O(V + E) each, or weighted union-find for near-O(1) queries after an O(E·α) build.
Approach 1 — Weighted-graph DFS per query
a / b = k is a bidirectional weighted edge: a → b with weight k and b → a with weight 1/k. Then x / y is the product of weights along any path from x to y; because the equations are consistent, every path gives the same product. For each query, DFS from x, accumulate the product, and stop when you reach y.
For equations [["a","b"],["b","c"]] with values [2,3], the graph is:
graph LR
a -->|2| b
b -->|0.5| a
b -->|3| c
c -->|1/3| b
from collections import defaultdict
def calcEquation(
self,
equations: list[list[str]],
values: list[float],
queries: list[list[str]],
) -> list[float]:
graph = defaultdict(dict)
for (a, b), k in zip(equations, values):
graph[a][b] = k
graph[b][a] = 1.0 / k
def dfs(src: str, dst: str, seen: set) -> float:
if src == dst:
return 1.0
seen.add(src)
for nei, w in graph[src].items():
if nei not in seen:
sub = dfs(nei, dst, seen)
if sub != -1.0:
return w * sub
return -1.0
out = []
for x, y in queries:
if x not in graph or y not in graph:
out.append(-1.0)
else:
out.append(dfs(x, y, set()))
return out
Walkthrough (equations [["a","b"],["b","c"]], values [2,3], query ["a","c"]):
- Graph:
a→b=2, b→a=0.5, b→c=3, c→b=1/3.
dfs("a","c"): from a, edge to b (w=2) → dfs("b","c"): from b, edge to c (w=3) → dfs("c","c") returns 1.0. So 3·1 = 3, then 2·3 = 6. Answer 6.0.- Query
["a","e"]: e not in graph → -1.0. Query ["x","x"]: x not in graph → -1.0 (note: x/x is 1 only for known x).
Complexity: each query traverses at most the whole component → O(V + E) per query, O(Q·(V + E)) total. Building the graph is O(E). Space O(V + E).
Approach 2 — BFS per query
Same model, but explored level by level with a queue that carries the running product to each node. BFS avoids recursion-depth limits when components are wide and shallow; DFS is terser and fine here since components are tiny (≤ 20 equations).
from collections import defaultdict, deque
def calcEquation(
self,
equations: list[list[str]],
values: list[float],
queries: list[list[str]],
) -> list[float]:
graph = defaultdict(dict)
for (a, b), k in zip(equations, values):
graph[a][b] = k
graph[b][a] = 1.0 / k
def bfs(src: str, dst: str) -> float:
if src not in graph or dst not in graph:
return -1.0
queue = deque([(src, 1.0)])
seen = {src}
while queue:
node, prod = queue.popleft()
if node == dst:
return prod
for nei, w in graph[node].items():
if nei not in seen:
seen.add(nei)
queue.append((nei, prod * w))
return -1.0
return [bfs(x, y) for x, y in queries]
Complexity: same as DFS — O(V + E) per query.
Approach 3 — Weighted union-find
All variables in one connected component are mutually determined, so pick a component root and store, for every node, its ratio node / root. Then x / y = (x / root) / (y / root) whenever x and y share a root, which is a constant-time division after path-compressed finds. Union-find (disjoint-set union) maintains the components; the extra step is carrying a multiplicative weight to the parent and compounding it during find’s path compression.
def calcEquation(
self,
equations: list[list[str]],
values: list[float],
queries: list[list[str]],
) -> list[float]:
parent: dict[str, str] = {}
weight: dict[str, float] = {} # weight[x] = value of x / parent[x]
def find(x: str) -> str:
if parent[x] != x:
root = find(parent[x])
weight[x] *= weight[parent[x]] # compound ratio to root
parent[x] = root
return parent[x]
def add(x: str) -> None:
if x not in parent:
parent[x], weight[x] = x, 1.0
for (a, b), k in zip(equations, values):
add(a)
add(b)
ra, rb = find(a), find(b)
if ra != rb:
# attach ra under rb, keeping a / b = k
parent[ra] = rb
weight[ra] = k * weight[b] / weight[a]
out = []
for x, y in queries:
if x not in parent or y not in parent or find(x) != find(y):
out.append(-1.0)
else:
out.append(weight[x] / weight[y])
return out
Walkthrough (equations [["a","b"],["b","c"]], values [2,3], query ["a","c"]):
- Union a,b (a/b=2): merge so ratios encode
a/root and b/root. Union b,c (b/c=3) chains c into the same component.
- After path compression each of
a,b,c stores its ratio to the shared root. For a/c, find(a)==find(c), so answer is weight[a] / weight[c] = 6.0.
Complexity: near O((E + Q)·α(V)) time with path compression (α = inverse Ackermann, effectively constant), O(V) space. Fastest when there are many queries against a fixed set of equations.
Common pitfalls
- Returning
1.0 for x / x when x never appears — it must be -1.0; guard with an “is this variable known?” check.
- Forgetting the reverse edge
b → a = 1/k, which disconnects otherwise-reachable variables.
- Floating-point: multiply, don’t accumulate error by re-deriving; the answers here are within tolerance so exact equality isn’t required.
- In weighted union-find, updating
weight[x] before recursively finding the root, or getting the union formula’s direction wrong. Derive the formula from a / b = k and the two nodes’ current ratios.
Pattern takeaway
Ratios, exchange rates, and unit conversions form a weighted graph where the answer is a product along a path. Per-query DFS/BFS is simplest and plenty fast for small graphs; when queries are numerous or the structure is fixed, weighted union-find collapses each component to per-node ratios against a root, turning each query into one division.