AAlgoLoopSpaced repetition for LeetCode
MEDIUMGraphLeetCode ↗

Evaluate Division

The key idea

Each equation Ai / Bi = values[i] is a directed weighted edge Ai -> Bi with weight values[i] and a reverse edge Bi -> Ai with weight 1 / values[i]. A query Cj / Dj is then just the product of edge weights along any path from Cj to Dj; if no path exists (or a variable is unknown) the answer is -1.0.

Problem

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 j-th 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.

The variables that do not occur in the list of equations are undefined, so a query asking about them returns -1.0. It is guaranteed that there is no contradiction and no division by zero in the input.

Constraints

Examples

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

Complexity

Time: O(q * (n + e)) Space: O(n + e)

See the full solution

410310
Step-by-step visualization
Start free →

More Graph problems