Evaluate Division — Solution

Problem

You're given a list of ratio equations — each one tells you the result of dividing one variable by another — along with a list of queries asking for other ratios. Return the numeric result of each query, or -1.0 if the answer can't be determined.

• Input: equations = [["a","b"],["b","c"]], values = [2.0, 3.0], queries = [["a","c"],["b","a"],["a","e"]]
• Output: [6.0, 0.5, -1.0]
• Explanation: a/b = 2.0 and b/c = 3.0, so a/c = 2.0 × 3.0 = 6.0; b/a = 1/2.0 = 0.5; e doesn't appear in any equation so -1.0.

Counter-example: querying x/x where x has never appeared in any equation should return -1.0 — you have no information about x at all, even though the ratio of any known variable to itself would be 1.0.

Intuition

Each equation a/b = k is really a relationship between two quantities that you can chain together. If a/b = 2 and b/c = 3, then a/c = a/b × b/c = 6 — you can reach the answer by multiplying along a path of intermediate ratios. The key insight is that this is a weighted graph problem: each variable is a node, each equation is a directed edge with weight equal to the quotient, and answering a query means finding a path between two nodes and multiplying all edge weights along that path.

Solution — BFS on a Weighted Graph

Build a bidirectional weighted graph from the equations, then run BFS for each query to find the path product from source to target.

1. For each equation a / b = k, add edge a → b with weight k and edge b → a with weight 1.0 / k.
2. For each query (src, dst):
   • If either variable is absent from the graph, return -1.0 (no information about it).
   • If src == dst, return 1.0.
   • Run BFS from src, tracking the accumulated product at each node.
   • When BFS reaches dst, return the accumulated product at that point.
   • If BFS exhausts all reachable nodes without finding dst, return -1.0.
3. Collect results across all queries and return them.

1from collections import defaultdict, deque
2from typing import List
3
4def calcEquation(equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
5    graph = defaultdict(dict)
6    for (numerator, denominator), value in zip(equations, values):
7        graph[numerator][denominator] = value
8        graph[denominator][numerator] = 1.0 / value  # reverse edge is the reciprocal
9
10    def bfs(source, target):
11        if source not in graph or target not in graph:
12            return -1.0
13        if source == target:
14            return 1.0
15
16        visited = {source}
17        queue = deque([(source, 1.0)])  # (current_node, accumulated_product)
18
19        while queue:
20            current_node, accumulated_product = queue.popleft()
21            for neighbor, edge_weight in graph[current_node].items():
22                new_product = accumulated_product * edge_weight
23                if neighbor == target:
24                    return new_product  # found path, return product of all edge weights
25                if neighbor not in visited:
26                    visited.add(neighbor)
27                    queue.append((neighbor, new_product))
28
29        return -1.0  # no path exists between source and target
30
31    return [bfs(src, dst) for src, dst in queries]

Time: O(E + Q·(V+E)) — building the graph takes O(E); each of Q queries runs a BFS that visits at most V nodes and E edges.

Space: O(V + E) — the graph stores each variable as a node and each equation as two directed edges; the BFS queue holds at most V nodes at once.

Complexity Summary

Common Mistakes

• Omitting reverse edges — from a/b = k you must add both a→b = k and b→a = 1/k; skipping the reverse means queries like b/a return -1.0 even though the answer is 0.5.
• Returning 1.0 for x/x without checking if x exists — if x never appeared in any equation, the answer is -1.0, not 1.0; always gate the source == target shortcut behind an existence check.
• Skipping the visited set — the graph can contain cycles (e.g. a→b→a); without tracking visited nodes the BFS loops forever.
• Accumulating products in the wrong direction — multiplying 1/edge_weight instead of edge_weight, or dividing instead of multiplying, produces wrong results; trace the example a→b=2, b→c=3 and verify a/c gives 6.0, not 0.167.
• Treating self-division as always valid — checking source == target before checking graph membership causes x/x to return 1.0 even for unknown variables; existence check must come first.

Related Problems

• number-of-provinces — same connected-components pattern; BFS/DFS identifies which nodes are reachable from a given source
• all-paths-from-source-to-target — BFS/DFS on a directed graph collecting all paths rather than a single weighted path
• cheapest-flights-within-k-stops — BFS on a weighted directed graph where the accumulated value along a path (cost) determines the answer
• word-ladder — BFS on an implicit graph; finding the shortest path between two nodes in an unweighted graph
• course-schedule — directed graph traversal where the structure of reachable nodes (cycles vs. none) determines the result