LeetCode 399: Evaluate Division

Problem Restatement

We are given equations representing division relationships between variables.

For example:

a / b = 2.0
b / c = 3.0

We are also given queries like:

a / c
c / a
a / e

We need to compute the value of each query.

If the query cannot be determined from the equations, return:

-1.0

The equations are guaranteed to be valid, and there is no contradiction. The number of equations and queries is at most 20, and all variable names are lowercase strings. (leetcode.com)

Input and Output

Item	Meaning
`equations[i] = [Ai, Bi]`	Represents `Ai / Bi`
`values[i]`	Numeric value of `Ai / Bi`
`queries[j] = [Cj, Dj]`	Query asking for `Cj / Dj`
Output	Array of query results
Unknown query	Return `-1.0`

Example function shape:

def calcEquation(
    equations: list[list[str]],
    values: list[float],
    queries: list[list[str]],
) -> list[float]:
    ...

Examples

Example 1:

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

The equations mean:

a / b = 2
b / c = 3

So:

a / c = 2 * 3 = 6
b / a = 1 / 2 = 0.5
a / e = unknown
a / a = 1
x / x = unknown

The answer is:

[6.0, 0.5, -1.0, 1.0, -1.0]

Example 2:

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

The answers are:

[3.75, 0.4, 5.0, 0.2]

First Thought: Store Every Pairwise Ratio

A direct idea is to compute all reachable ratios in advance.

For example:

a / b = 2
b / c = 3

implies:

a / c = 6
c / a = 1 / 6

We could try to build all relationships.

But graph traversal naturally solves this without computing everything upfront.

Key Insight

The equations form a weighted graph.

For:

a / b = 2

create edges:

a -> b with weight 2
b -> a with weight 1/2

Then answering a query becomes a graph path problem.

Example:

a -> b -> c

Weights:

2 * 3 = 6

So:

a / c = 6

We can use DFS or BFS to search for a path and multiply edge weights along the way.

Graph Construction

For each equation:

Ai / Bi = value

add two directed edges:

graph[Ai].append((Bi, value))
graph[Bi].append((Ai, 1 / value))

This lets us move in both directions.

Algorithm

Build the graph.

For each query [start, end]:

If either variable does not exist, return -1.0.
If start == end, return 1.0.
Otherwise, run DFS:
- Start with product 1.0.
- Multiply edge weights while traversing.
- If we reach end, return the accumulated product.
If no path exists, return -1.0.

Correctness

Each equation:

a / b = v

is represented by two graph edges:

a -> b with weight v
b -> a with weight 1 / v

So every graph path corresponds to multiplying known division relationships.

Suppose DFS follows the path:

x0 -> x1 -> x2 -> ... -> xk

with edge weights:

w1, w2, ..., wk

Then the product:

w1 * w2 * ... * wk

equals:

x0 / xk

because intermediate variables cancel algebraically.

DFS explores all reachable variables from the start node. If a path to the target exists, DFS eventually reaches it and returns the correct product. If no path exists, then the division value cannot be derived from the equations, so returning -1.0 is correct.

Special cases are also correct:

Case	Result
Unknown variable	`-1.0`
`x / x` where `x` exists	`1.0`
No path between variables	`-1.0`

Complexity

Let:

Symbol	Meaning
`E`	Number of equations
`Q`	Number of queries
`V`	Number of variables

For each query, DFS may visit all vertices and edges.

Metric	Value
Time	`O(Q * (V + E))`
Space	`O(V + E)`

The graph stores all equations and reverse equations.

Implementation

from collections import defaultdict

class Solution:
    def calcEquation(
        self,
        equations: list[list[str]],
        values: list[float],
        queries: list[list[str]],
    ) -> list[float]:

        graph = defaultdict(list)

        for (a, b), value in zip(equations, values):
            graph[a].append((b, value))
            graph[b].append((a, 1 / value))

        def dfs(current, target, product, visited):
            if current == target:
                return product

            visited.add(current)

            for neighbor, weight in graph[current]:
                if neighbor not in visited:
                    result = dfs(
                        neighbor,
                        target,
                        product * weight,
                        visited,
                    )

                    if result != -1.0:
                        return result

            return -1.0

        answers = []

        for start, end in queries:
            if start not in graph or end not in graph:
                answers.append(-1.0)
            elif start == end:
                answers.append(1.0)
            else:
                answers.append(
                    dfs(start, end, 1.0, set())
                )

        return answers

Code Explanation

We build a weighted adjacency list:

graph = defaultdict(list)

For each equation:

a / b = value

store both directions:

graph[a].append((b, value))
graph[b].append((a, 1 / value))

The DFS function keeps:

Variable	Meaning
`current`	Current variable
`target`	Desired variable
`product`	Product along the current path
`visited`	Prevents cycles

If we reach the target:

if current == target:
    return product

Otherwise, explore neighbors:

for neighbor, weight in graph[current]:

The recursive call multiplies the path product:

product * weight

If no path succeeds:

return -1.0

For each query:

for start, end in queries:

handle unknown variables:

if start not in graph or end not in graph:

handle identical variables:

elif start == end:

otherwise run DFS.

Alternative: Union-Find With Weights

This problem can also be solved using weighted Union-Find.

Each node stores:

Value	Meaning
`parent[x]`	Representative node
`weight[x]`	Ratio between `x` and `parent[x]`

This gives near-constant-time queries after preprocessing.

However, DFS is simpler and sufficient for the problem constraints.

Testing

def test_solution():
    s = Solution()

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

    result = s.calcEquation(equations, values, queries)

    expected = [6.0, 0.5, -1.0, 1.0, -1.0]

    for a, b in zip(result, expected):
        assert abs(a - b) < 1e-9

    equations = [["a", "b"], ["b", "c"], ["c", "d"]]
    values = [2.0, 3.0, 4.0]
    queries = [["a", "d"], ["d", "a"]]

    result = s.calcEquation(equations, values, queries)

    assert abs(result[0] - 24.0) < 1e-9
    assert abs(result[1] - (1 / 24.0)) < 1e-9

    equations = [["x", "y"]]
    values = [5.0]
    queries = [["x", "x"], ["y", "y"], ["x", "z"]]

    result = s.calcEquation(equations, values, queries)

    assert result == [1.0, 1.0, -1.0]

    print("all tests passed")

test_solution()

Test meaning:

Test	Why
Chain `a -> b -> c`	Multi-edge multiplication
Reverse direction	Reciprocal edge correctness
Unknown variable	Return `-1.0`
Same variable	Return `1.0` when known
Longer chain	Multiple edge traversal
Disconnected query	No path exists