AlgorithmsGraphsLeetCode SolutionsMedium DifficultyPythonRecursionRecursive DFSUnion Find

# [LeetCode 399] Evaluate Division

You are given an array of variable pairs `equations` and an array of real numbers `values`, where `equations[i] = [Ai, Bi]` and `values[i]` represent the equation `Ai / Bi = values[i]`. Each `Ai` or `Bi` is a string that represents a single variable.

You are also given some `queries`, where `queries[j] = [Cj, Dj]` represents the `jth` query where you must find the answer for `Cj / Dj = ?`.

Return the answers to all queries. If a single answer cannot be determined, return `-1.0`.

Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.

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]
Explanation:
Given: a / b = 2.0, b / c = 3.0
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
return: [6.0, 0.5, -1.0, 1.0, -1.0 ]
```

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

Example 3:

```Input: equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
Output: [0.50000,2.00000,-1.00000,-1.00000]
```

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

Time complexity – O(MN) for M queries

Space complexity – O(2N) for outgoing + O(M*N) visited + O(N) queue

## RECURSIVE DFS

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

graph = defaultdict(defaultdict)

def backtrack_evaluate(curr_node, target_node, acc_product, visited):
visited.add(curr_node)
ret = -1.0
neighbors = graph[curr_node]
if target_node in neighbors:
ret = acc_product * neighbors[target_node]
else:
for neighbor, value in neighbors.items():
if neighbor in visited:
continue
ret = backtrack_evaluate(
neighbor, target_node, acc_product * value, visited)
if ret != -1.0:
break
visited.remove(curr_node)
return ret

# Step 1). build the graph from the equations
for (dividend, divisor), value in zip(equations, values):
# add nodes and two edges into the graph
graph[dividend][divisor] = value
graph[divisor][dividend] = 1 / value

# Step 2). Evaluate each query via backtracking (DFS)
#  by verifying if there exists a path from dividend to divisor
results = []
for dividend, divisor in queries:
if dividend not in graph or divisor not in graph:
# case 1): either node does not exist
ret = -1.0
elif dividend == divisor:
# case 2): origin and destination are the same node
ret = 1.0
else:
visited = set()
ret = backtrack_evaluate(dividend, divisor, 1, visited)
results.append(ret)

return results```
```class Solution:
def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
table = collections.defaultdict(dict)
for (x, y), val in zip(equations, values):
table[x][y] = val
table[y][x] = 1.0/val
ans = [self.dfs(x, y, table, set()) if x in table and y in table else -1.0 \
for (x, y) in queries]
return ans

def dfs(self, x, y , table, visited):
if x == y:
return 1.0
visited.add(x)
for n in table[x]:
if n in visited:
continue
visited.add(n)
d = self.dfs(n, y, table, visited)
if d > 0:
return d * table[x][n]
return -1.0       ```

## UNION FIND

```from collections import defaultdict
class Solution:
def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
# union find

self.root = {}

for (dividend, divisor), val in zip(equations, values):
self.union(dividend, divisor, val)

output = []
for dividend, divisor in queries:
if dividend not in self.root or divisor not in self.root:
output.append(-1)
else:
dividend_id, dividend_val = self.find(dividend)
divisor_id, divisor_val = self.find(divisor)

if dividend_id != divisor_id:
output.append(-1)
else:
output.append(dividend_val/ divisor_val)

return output

def union(self, dividend, divisor, val):
# init and union dividend and divisor
fdividend, rdividend = self.find(dividend)
fdivisor, rdivisor = self.find(divisor)
if fdividend != fdivisor:
self.root[fdividend] = (fdivisor, rdivisor * val/rdividend)

def find(self, node):
if node not in self.root:
self.root[node] = (node, 1)
fnode, fval = self.root[node]
if node != fnode:
new_fnode, new_val = self.find(fnode)
self.root[node] = (new_fnode, fval * new_val)

return self.root[node]```
Previous Post

Next article