MediumArrayDepth-First SearchUnion FindGraphShortest Path

Evaluate Division

1 approach, code in every language

You are given a list of equations of the form a / b = value, where a and b are variable names and value is a real number. From these known ratios you may derive other ratios by chaining divisions together, for example if a / b and b / c are known, then a / c is their product.

For each query of the form c / d, compute the resulting value using only the equations provided. If the answer cannot be determined, either because a variable never appears in any equation or because no chain of divisions connects the two variables, return -1.0 for that query.

Return an array holding the answer to every query in the same order the queries are given.

Example 1

Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]

Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]

a/c = (a/b)*(b/c) = 2*3 = 6, b/a = 1/2 = 0.5, e is unknown so a/e is -1, a/a is 1, and x never appears so x/x is -1.

Example 2

Input: equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]

Output: [3.75000,0.40000,5.00000,0.20000]

a/c = 1.5*2.5 = 3.75, c/b = 1/2.5 = 0.4, bc/cd is given as 5.0, and cd/bc is its reciprocal 0.2.

Constraints

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 lowercase English letters and digits.

Weighted Graph DFS

Model variables as graph nodes with division ratios as edge weights, then multiply weights along a path from source to target.

Loading animation…

Intuition

A division a / b = value is really a directed connection from a to b with a weight equal to value, and the reverse connection from b to a naturally carries weight 1 / value. Once every equation is expressed this way, evaluating a query becomes the task of finding a path from the source variable to the target variable. Multiplying all the edge weights along that path telescopes the intermediate variables and leaves exactly the ratio we want. A depth-first search explores possible paths, and marking visited nodes prevents cycles from looping forever. If the search never reaches the target, or if either variable was never seen, the query is undetermined and we return -1.0.

Algorithm walkthrough

1Build an adjacency structure where each variable maps to its neighbors together with the division ratio on that edge.
2For every equation add a forward edge weighted by the value and a backward edge weighted by its reciprocal.
3For each query, first confirm both variables exist in the graph; if either is missing, record -1.0.
4Run a depth-first search from the source, carrying the accumulated product and a visited set to avoid revisiting nodes.
5When the search reaches the target, multiply the current edge weight by the result returned from the recursion and propagate it back up.
6If no neighbor leads to the target, return -1.0 so the caller knows the query is unresolved.

Implementation

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        graph = defaultdict(dict)
        for (a, b), v in zip(equations, values):
            graph[a][b] = v
            graph[b][a] = 1.0 / v

        def dfs(src, dst, visited):
            if src not in graph or dst not in graph:
                return -1.0
            if src == dst:
                return 1.0
            visited.add(src)
            for neighbor, weight in graph[src].items():
                if neighbor in visited:
                    continue
                sub = dfs(neighbor, dst, visited)
                if sub != -1.0:
                    return weight * sub
            return -1.0

        result = []
        for c, d in queries:
            result.append(dfs(c, d, set()))
        return result

Time

O(q * (V + E))

Space

O(V + E)

Building the graph is O(E). Each of the q queries runs a DFS that in the worst case visits every vertex V and edge E.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Stacks & Queues

After the pattern

Now solve one you haven't seen.

Gear Train Ratios is our own problem on the technique behind Evaluate Division: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free