Evaluate Division Medium 0 attempts
LeetCode ↗

Evaluate Division

Medium GraphBFSDFS LeetCode

You're given a list of division equations, such as a / b = 2.0, along with their results in values, and a list of queries asking for the result of other divisions, such as a / c. Using the known equations, work out the answer to each query; if a query's result can't be derived from the given equations, report -1.0 for it instead.

Input Format
Implement calcEquation(equations, values, queries). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement. Floating-point results are compared with relative tolerance 0.00001.

Sample Input and Output

Example 1 · Run Sample

Input
equations = [["a","b"],["b","c"]]
values = [2,3]
queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output
[6,0.5,-1,1,-1]

Example 2

Input
equations = [["x","y"]]
values = [4]
queries = [["y","x"],["x","z"]]
Output
[0.25,-1]
Constraints
  • 1 <= equations.length <= 20
  • 1 <= queries.length <= 20
  • values[i] > 0
Test Cases (2)
Case 1
Args: [[["a","b"],["b","c"]],[2,3],[["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]] Expected: [6,0.5,-1,1,-1]
Case 2
Args: [[["x","y"]],[4],[["y","x"],["x","z"]]] Expected: [0.25,-1]
Topics
GraphBFSDFS

Graph DFS

Build a weighted graph, DFS from dividend to divisor multiplying weights.

javascript
function calcEquation(equations, values, queries) {
  const graph = new Map();
  for (let i = 0; i < equations.length; i++) {
    const [a, b] = equations[i], v = values[i];
    if (!graph.has(a)) graph.set(a, []);
    if (!graph.has(b)) graph.set(b, []);
    graph.get(a).push([b, v]); graph.get(b).push([a, 1/v]);
  }
  function dfs(src, dst, visited) {
    if (!graph.has(src) || !graph.has(dst)) return -1;
    if (src === dst) return 1;
    visited.add(src);
    for (const [next, w] of graph.get(src)) {
      if (visited.has(next)) continue;
      const res = dfs(next, dst, visited);
      if (res !== -1) return w * res;
    }
    return -1;
  }
  return queries.map(([a, b]) => dfs(a, b, new Set()));
}

Time: O(Q × (V + E)) | Space: O(V + E)

Saved in this browser only. Private to you.

JavaScript