Python O(N^3 + Q) solution


  • 0

    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]):
                zeroes.add(x)
            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

  • 0

    @SergeyTachenov said in Python O(N^3 + Q) solution:

    where N is the number of equations

    I think you mean number of variables, no?


  • 0

    @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.


Log in to reply
 

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