#399 - Evaluate Division

MediumGraphs - DFS

You are given equations like a / b = k and queries [c, d]. Return the answer for each query, or -1.0 if the answer cannot be determined. Variables that appear in equations are connected via multiplication/division.

Input	Output
`equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]`	`[6.0, 0.5, -1.0, 1.0, -1.0]`

Solution

Try it

/**
 * Evaluates division queries using a weighted directed graph.
 * Each equation a/b = k creates edges a→b (weight k) and b→a (weight 1/k).
 * A query c/d is answered by finding a path from c to d and multiplying edge weights.
 *
 * @param equations Variable pairs [numerator, denominator]
 * @param values    Division results for each equation
 * @param queries   Pairs to evaluate
 * @returns         Query results (-1.0 if undetermined)
 */
export function calcEquation(
  equations: string[][],
  values: number[],
  queries: string[][],
): number[] {
  // Build weighted adjacency list
  const graph = new Map<string, Map<string, number>>();

  for (let i = 0; i < equations.length; i++) {
    const [a, b] = equations[i];
    if (!graph.has(a)) graph.set(a, new Map());
    if (!graph.has(b)) graph.set(b, new Map());
    graph.get(a)!.set(b, values[i]);
    graph.get(b)!.set(a, 1 / values[i]);
  }

  function dfs(src: string, dst: string, visited: Set<string>): number {
    if (!graph.has(src) || !graph.has(dst)) return -1;
    if (src === dst) return 1;

    visited.add(src);

    for (const [neighbor, weight] of graph.get(src)!) {
      if (visited.has(neighbor)) continue;
      const result = dfs(neighbor, dst, visited);
      if (result !== -1) return weight * result;
    }

    return -1;
  }

  return queries.map(([c, d]) => dfs(c, d, new Set()));
}

Approach: weighted graph DFS – build a graph where `a → b` has weight `a/b`. To evaluate `c/d`, DFS from `c` to `d` multiplying edge weights along the path.

Time: O(Q · (V + E)) – for Q queries, each DFS visits up to V + E nodes/edges.

Space: O(V + E) – adjacency list storage.

Alternative approaches:

Approach	Idea	Time	Space
BFS	Same graph, BFS instead of DFS for each query	O(Q · (V + E))	O(V + E)
Union-Find with weights	Track ratio to root for each variable; query = ratio division	O((V + E) · α(V) + Q)	O(V)

Why DFS is preferred: most intuitive approach for graph path-finding with weight multiplication; Union-Find is faster for many queries but trickier to implement correctly with weights.