Evaluate Division

Evaluate Division hard

Description

You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [A_i, B_i] and values[i] represent the equation A_i / B_i = values[i]. Each A_i or B_i is a string that represents a single variable.

You are also given some queries, where queries[j] = [C_j, D_j] represents the jth query where you must find the answer for C_j / D_j = ?.

Return the answers to all queries. If a single answer cannot be determined, return -1.0.

The input is always valid. You may assume division by zero does not occur, and no contradictions.

Examples

> Case 1:
    equations = [["a","b"],["b","c"]]
    values = [2.0, 3.0]
    queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
    Output: [6.0, 0.5, -1.0, 1.0, -1.0]

Constraints

1 <= equations.length <= 20
equations[i].length == 2
1 <= A_i.length, B_i.length <= 5
values[i] > 0.0
1 <= queries.length <= 20

State design

A division graph: a / b = 2 is a directed weighted edge a → b with weight 2 (and implicitly b → a with weight 0.5). A query c / d = ? asks for the product of edge weights along any c ⤳ d path. If c and d are in different components, return -1.0.

DFS approach is straightforward: build an adjacency map and DFS from c, tracking the cumulative product until d is reached.

Weighted Union Find is more elegant for repeated queries: each find(x) returns the root AND maintains weight[x] = the multiplicative ratio x / root(x). Then c / d = weight[c] / weight[d] whenever they share a root.

The wiring:

find(x) recurses to find the root and accumulates the weight from x to the root.
union(x, y, val) (meaning x / y = val) joins the two roots and sets the connecting weight so the invariants stay consistent.

# find returns root, and updates weight[x] to mean "x / root"
def find(x):
    if parent[x] != x:
        root = find(parent[x])
        weight[x] *= weight[parent[x]]    # accumulate
        parent[x] = root
    return parent[x]
 
# union(x, y, val): means x = val * y
def union(x, y, val):
    rx, ry = find(x), find(y)
    if rx == ry:
        return
    # Want: weight[rx] (= rx / ry once connected) such that
    #   x / y = (x / rx) * (rx / ry) * (ry / y) = val
    #   weight[x] * weight[rx] / weight[y] = val
    parent[rx] = ry
    weight[rx] = val * weight[y] / weight[x]

For queries: if find(c) != find(d) → unknown → -1.0. Otherwise → weight[c] / weight[d].

Code

Analysis

Time: O((N + Q) · α(N)) — DSU near-constant per operation.
Space: O(N) for the maps.

Alternative — DFS / BFS

Plain DFS from c chasing the multiplicative chain to d works in O(N · Q). Often the more “interview-natural” solution; weighted DSU is the elegant one for follow-up “what if there are many queries?”.

Weighted DSU is the lesson. The technique generalizes to: parity (“is x on the same team as y?”), distance (“how far is x from y?”), and any algebraic offset where the merge can be expressed in the group’s operation. Same skeleton, different operator.

Same skin

Satisfiability of Equality Equations — plain DSU (additive equivalence).
Possible Bipartition — weighted DSU with parity (XOR).
Currency Arbitrage — multiplicative graph, but with cycle-detection instead of queries.

Regions Cut By Slashes Overview