# 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]
# Solution
Approach 1: use the idea of Union Find. The key to this problem is how to figure out whether two variables are connected. It can be done with a search (dfs/bfs), but union find is asymptotically faster, since it compresses paths to the root.
# Code (Python)
Approach 1:
Approach 2:
# Code (C++)
Approach 1:
Approach 2:
# Code (Typescript)
Approach 1:
function calcEquation(equations: string[][], values: number[], queries: string[][]): number[] {
// The key to this problem is how to figure out whether two variables are 'connected'.
// It can be done with a search (dfs/bfs), but union find is asymptotically faster,
// since it compresses paths to the root, so tree is shallow.
// stores {node: [root, weight]}
const parent: { [key: string]: [string, number] } = {};
// finds the root, and ratio of nodeValue / rootValue
function findRoot(node: string): [string, number] {
// base case: root is self
if (!(node in parent)) {
parent[node] = [node, 1];
return parent[node];
}
// recursive case: flatten the path so that parent[node] is the root for all nodes along the path
const [immediateParent, parentWeight] = parent[node];
if (immediateParent !== node) {
const [root, weight] = findRoot(immediateParent);
parent[node] = [root, weight * parentWeight];
}
return parent[node]
}
for (let i = 0; i < equations.length; i++) {
let [numerator, denominator] = equations[i];
let [numeratorRoot, numeratorWeight] = findRoot(numerator);
let [denominatorRoot, denominatorWeight] = findRoot(denominator);
// if they're in the same group, should really check for consistency, but this problem guarantees consistency
if (numeratorRoot !== denominatorRoot) {
// merge two groups by connecting one group's root to another group's root
parent[numeratorRoot] = [denominatorRoot, denominatorWeight * values[i] / numeratorWeight];
}
}
const result = [];
for (let [node1, node2] of queries) {
if (!parent[node1] || !parent[node2]) {
result.push(-1);
} else if (node1 === node2) {
result.push(1);
} else {
let [root1, weight1] = findRoot(node1);
let [root2, weight2] = findRoot(node2);
if (root1 !== root2) {
result.push(-1);
} else {
result.push(weight1 / weight2);
}
}
}
return result;
};