# Python O(N^3 + Q) solution

• If x / y = a, then x = ay. If a = 0, then x = 0, otherwise we don't know what x is, but then we also know that y = x / a and we can establish a dictionary of such equations for every variable. After we have it, we expand them recursively, so that we have a x = ay equation for every (x, y) for which it is possible to figure out the equation. Worst-case complexity of this part is O(N^3), where N is the number of equations variables, there are O(N^2) (x, y) pairs and for each pair we consider all z's so that we can compute x / z from x / y and y / z. This is similar to Floyd-Warshall algorithm, which I didn't know at the time of writing.

Then, for any x and y we can check the sets of these equations. If they contain no common variables, then equations for x and y must be independent and therefore we return -1. Otherwise, if we know that x = az and y = bz, then x / y = a / b. As a special case, if x is known to be zero, then x / y is zero for any possible y even if it isn't mentioned anywhere in the equations.

``````    eqs_for = dict((x, {x: 1})
for eq in equations
for x in eq)
eqs_for.update(dict((eq[0], {eq[1]: float(val)})
for eq, val in zip(equations, values)))
eqs_for.update(dict((eq[1], {eq[0]: 1 / float(val)})
for eq, val in zip(equations, values) if val != 0))
zeroes = set(eq[0] for eq, val in zip(equations, values) if val == 0)

def expand(x, y):
if any(z in zeroes for z in eqs_for[y]):
for z in set(eqs_for[y].keys()) - set(eqs_for[x].keys()):
eqs_for[x][z] = eqs_for[x][y] * eqs_for[y][z]
expand(x, z)

for x in eqs_for:
for y in eqs_for[x].keys():
expand(x, y)
res = []
for x, y in query:
if x in zeroes:
res.append(0)
elif x not in eqs_for or y not in eqs_for:
res.append(-1)
else:
common = set(eqs_for[x].keys()) & set(eqs_for[y].keys())
if not common:
res.append(-1)
else:
z = common.pop()
res.append(eqs_for[x][z] / eqs_for[y][z])
return res``````

• where N is the number of equations

I think you mean number of variables, no?

• @StefanPochmann Yes, of course. I haven't realized that by turning the whole thing into a dictionary, I removed duplicates. The magnitude should be roughly the same, though, unless we have a test that goes like `a / b = 1, a / b = 1, a / b = 1,...`, which is certainly possible.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.