AlgoMaster Logo

Evaluate Division

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

This problem is about chaining division relationships. If we know a / b = 2 and b / c = 3, then a / c = a/b * b/c = 6. Given a set of these relationships, we need to resolve arbitrary division queries.

These equations form a weighted directed graph. Each variable is a node, and each equation a / b = k creates two directed edges: one from a to b with weight k, and one from b to a with weight 1/k. Resolving a / c becomes finding a path from node a to node c, where the answer is the product of all edge weights along the path.

If there's no path between two variables, the answer is -1.0. If a variable doesn't even exist in the graph, the answer is also -1.0.

Key Constraints:

  • 1 <= equations.length <= 20 -> At most 40 distinct variables. Even an O(V^3) algorithm like Floyd-Warshall finishes instantly, so any of the approaches below fits comfortably.
  • 1 <= queries.length <= 20 -> Few queries. Running a separate BFS or DFS for each query stays well within limits.
  • 0.0 < values[i] <= 20.0 -> All values are positive. There is no division by zero and no negative edge weights.

Approach 1: BFS (Graph Traversal)

Intuition

Build a weighted directed graph where each equation a / b = k creates edges a -> b with weight k and b -> a with weight 1/k. For each query c / d, run a BFS from c to d. If we reach d, the answer is the product of all edge weights along the path. If c or d is absent from the graph, or there is no path between them, the answer is -1.0.

Any path from c to d gives the correct ratio, because the product of edge weights telescopes: along c -> x -> d, the product is (c/x) * (x/d) = c/d. The problem guarantees no contradictions, so every path between two nodes yields the same product, and BFS can return as soon as it reaches the target.

Algorithm

  1. Build an adjacency list: for each equation a / b = k, add (b, k) to a's neighbor list and (a, 1/k) to b's neighbor list.
  2. For each query (source, target):
    • If either variable is not in the graph, return -1.0.
    • If source equals target, return 1.0.
    • Run BFS from source. Maintain a queue of (node, accumulated_product) pairs. Start with (source, 1.0).
    • Track visited nodes to avoid cycles.
    • When we dequeue a node, check all its neighbors. Multiply the current product by the edge weight. If we reach the target, return the product.
    • If BFS completes without finding the target, return -1.0.

Visualization and Code

Loading animation...

Each query runs an independent BFS. The next approach precomputes all pairwise division results once, turning every query into a table lookup.

Approach 2: Floyd-Warshall (All-Pairs Precomputation)

Intuition

Floyd-Warshall is normally used for all-pairs shortest paths, but the same triple loop works for all-pairs division. Instead of minimizing summed distances, we compute products along paths.

Create a matrix dist[i][j] that holds the result of variable_i / variable_j. Initialize it with the known equations and their inverses, then run the Floyd-Warshall relaxation. For each intermediate variable k, if both dist[i][k] and dist[k][j] are known, then i / j can be computed as (i / k) * (k / j), so set dist[i][j] = dist[i][k] * dist[k][j].

After running Floyd-Warshall, every query becomes an O(1) table lookup.

Algorithm

  1. Assign each unique variable an integer index (0, 1, 2, ...).
  2. Create a 2D matrix dist of size V x V, initialized to -1.0. Set dist[i][i] = 1.0 for all i (any variable divided by itself is 1).
  3. For each equation a / b = k, set dist[index(a)][index(b)] = k and dist[index(b)][index(a)] = 1/k.
  4. Run Floyd-Warshall: for each intermediate node k, for each pair (i, j), if dist[i][k] and dist[k][j] are both known (not -1), set dist[i][j] = dist[i][k] * dist[k][j].
  5. For each query (c, d): if either variable is unknown, return -1.0. Otherwise, return dist[index(c)][index(d)].

Visualization and Code

Loading animation...

Floyd-Warshall computes every pair upfront, including pairs that are never queried. The next approach groups connected variables with weighted Union Find and resolves each query from a stored ratio to the component root.

Approach 3: Union Find (Weighted)

Intuition

Union Find (Disjoint Set Union) groups elements into connected components. The weighted variant tracks a ratio between each element and its root. If a/root = x and b/root = y, then a/b = x/y.

For each equation a / b = k, union the sets containing a and b. Each node stores a weight equal to the ratio of its value to its parent's value. To answer a / b, find both roots. If they match, a and b are in the same component and a/b = weight[a] / weight[b]. If the roots differ, the answer is -1.0.

Path compression needs care here. When the path from a node to its root is flattened, the weight has to be updated to the direct ratio to the new root, not just to the old parent.

Algorithm

  1. Initialize a parent map and a weight map. Each variable starts as its own parent with weight 1.0.
  2. Define find(x): find the root of x with path compression. During compression, update weight[x] = weight[x] * weight[parent[x]] so that weight[x] represents x / root.
  3. Define union(a, b, k) where a / b = k: find roots of a and b. If different, set parent[rootA] = rootB and compute the correct weight: weight[rootA] = k * weight[b] / weight[a].
  4. Process all equations using union.
  5. For each query (c, d): if either is unknown, return -1.0. Find their roots. If roots differ, return -1.0. Otherwise, return weight[c] / weight[d].

Visualization and Code

Loading animation...