# LeetCode 399: Evaluate Division

## Problem Restatement

We are given equations representing division relationships between variables.

For example:

```python
a / b = 2.0
b / c = 3.0
```

We are also given queries like:

```python
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:

```python
-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](https://leetcode.com/problems/evaluate-division/?utm_source=chatgpt.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:

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

## Examples

Example 1:

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

The equations mean:

```text
a / b = 2
b / c = 3
```

So:

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

The answer is:

```python
[6.0, 0.5, -1.0, 1.0, -1.0]
```

Example 2:

```python
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:

```python
[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:

```text
a / b = 2
b / c = 3
```

implies:

```text
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:

```python
a / b = 2
```

create edges:

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

Then answering a query becomes a graph path problem.

Example:

```text
a -> b -> c
```

Weights:

```text
2 * 3 = 6
```

So:

```text
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:

```python
Ai / Bi = value
```

add two directed edges:

```python
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]`:

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

## Correctness

Each equation:

```text
a / b = v
```

is represented by two graph edges:

```text
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:

```text
x0 -> x1 -> x2 -> ... -> xk
```

with edge weights:

```text
w1, w2, ..., wk
```

Then the product:

```text
w1 * w2 * ... * wk
```

equals:

```text
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

```python
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:

```python
graph = defaultdict(list)
```

For each equation:

```python
a / b = value
```

store both directions:

```python
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:

```python
if current == target:
    return product
```

Otherwise, explore neighbors:

```python
for neighbor, weight in graph[current]:
```

The recursive call multiplies the path product:

```python
product * weight
```

If no path succeeds:

```python
return -1.0
```

For each query:

```python
for start, end in queries:
```

handle unknown variables:

```python
if start not in graph or end not in graph:
```

handle identical variables:

```python
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

```python
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 |