30 · Advanced Graphs: Euler Paths, Bridges & SCCs
#399 Evaluate Division
the problem
In plain words
You get facts of the form a / b = k: equations[i] = [a, b] with the value values[i]. Variable names are short strings of lowercase letters and digits. For each query [c, d], work out c / d from the facts. If it can't be worked out — for example, a variable never appears in any fact — answer -1.0. The facts never contradict each other and never divide by zero.
in equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
out [6.0,0.5,-1.0,1.0,-1.0]
a / c = (a / b) · (b / c) = 2 · 3. b / a = 1 / 2. e and x appear in no equation.
in equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
out [3.75,0.4,5.0,0.2]
in equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
out [0.5,2.0,-1.0,-1.0]
- 1 ≤ equations.length ≤ 20, values.length == equations.length
- 0.0 < values[i] ≤ 20.0
- 1 ≤ queries.length ≤ 20
- Names have 1–5 lowercase letters or digits
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternGraph DFS / BFS traversalUnion-Find (DSU)
where this runsUnit converters store a few factors and multiply along a chain — km → m → cm — exactly this weighted graph.
Turn each fact into two weighted edges: a → b with weight a/b and b → a with weight b/a. Then c / d is the product of the weights along any path from c to d. No path, or a variable you've never seen → -1.0.
solutions
From brute force to optimal
Number the variables, fill a ratio table with the given facts, then use every variable as a middle step (Floyd–Warshall style) until all derivable ratios are known. Each query is a lookup.
- Give each variable an index; ratio[i][i] = 1, ratio[a][b] = v, ratio[b][a] = 1 / v.
- For each middle m, for each pair (i, j): if ratio[i][j] is unknown and ratio[i][m], ratio[m][j] are known, set it to their product.
- Answer each query from the table (-1 for unknown names or empty cells).
Three nested loops over the V ≤ 40 variables, then O(1) per query.
The ratio table has one cell per pair of variables.
class Solution { /** Work out EVERY ratio first (Floyd–Warshall style), then answer each query by lookup. */ public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) { Map<String, Integer> id = new HashMap<>(); for (List<String> e : equations) for (String s : e) id.putIfAbsent(s, id.size()); int n = id.size(); double[][] ratio = new double[n][n]; // ratio[i][j] = i / j; 0 = not known yet for (int i = 0; i < n; i++) ratio[i][i] = 1.0; for (int k = 0; k < equations.size(); k++) { int a = id.get(equations.get(k).get(0)), b = id.get(equations.get(k).get(1)); ratio[a][b] = values[k]; ratio[b][a] = 1.0 / values[k]; } for (int m = 0; m < n; m++) // allow m as a middle variable: i / j = (i / m) * (m / j) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (ratio[i][j] == 0 && ratio[i][m] != 0 && ratio[m][j] != 0) ratio[i][j] = ratio[i][m] * ratio[m][j]; double[] answers = new double[queries.size()]; for (int q = 0; q < queries.size(); q++) { Integer c = id.get(queries.get(q).get(0)), d = id.get(queries.get(q).get(1)); answers[q] = c == null || d == null || ratio[c][d] == 0 ? -1.0 : ratio[c][d]; } return answers; }}Build Map<String, Map<String, Double>>. For each query, DFS from c carrying the running product; when you reach d, that product is c / d.
- For each fact: graph[a][b] = v and graph[b][a] = 1 / v.
- Query [c, d]: if either is missing from the graph, answer -1.
- Else walk(c, d, 1.0): reached d → return the product; otherwise mark seen and try each unseen neighbour with product × weight.
Each query's DFS visits every variable and edge at most once. At LeetCode's limits that's 20 × (40 + 40) steps.
The graph, plus a seen set and recursion depth of at most V per query.
class Solution { public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) { Map<String, Map<String, Double>> graph = new HashMap<>(); // graph.get(a).get(b) = a / b for (int i = 0; i < equations.size(); i++) { String a = equations.get(i).get(0), b = equations.get(i).get(1); graph.computeIfAbsent(a, k -> new HashMap<>()).put(b, values[i]); graph.computeIfAbsent(b, k -> new HashMap<>()).put(a, 1.0 / values[i]); } double[] answers = new double[queries.size()]; for (int q = 0; q < queries.size(); q++) { String c = queries.get(q).get(0), d = queries.get(q).get(1); if (!graph.containsKey(c) || !graph.containsKey(d)) answers[q] = -1.0; // never seen else answers[q] = walk(c, d, 1.0, graph, new HashSet<>()); } return answers; } /** product = start / cur so far. Returns start / target, or -1 if target can't be reached. */ private double walk(String cur, String target, double product, Map<String, Map<String, Double>> graph, Set<String> seen) { if (cur.equals(target)) return product; seen.add(cur); for (Map.Entry<String, Double> edge : graph.get(cur).entrySet()) { if (seen.contains(edge.getKey())) continue; double result = walk(edge.getKey(), target, product * edge.getValue(), graph, seen); if (result != -1.0) return result; } return -1.0; // dead end: back up }}Dry run
Union-find where each variable also stores weight(x) = x / parent(x). After find() flattens the path, weight(x) = x / root, so c / d = weight(c) / weight(d) when they share a root.
- union(a, b, v): find both roots; hang a's root under b's root with weight v · weight(b) / weight(a).
- find(x): recurse to the root, then multiply x's weight by its parent's and point x straight at the root.
- Query: unknown name or different roots → -1; else weight(c) / weight(d).
Path compression alone makes each find amortized O(log V) (α(V) with union by size too); map lookups are O(1) on average.
Two maps with one entry per variable.
class Solution { private Map<String, String> parent; private Map<String, Double> weight; // weight.get(x) = x / parent(x) public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) { parent = new HashMap<>(); weight = new HashMap<>(); for (int i = 0; i < equations.size(); i++) union(equations.get(i).get(0), equations.get(i).get(1), values[i]); double[] answers = new double[queries.size()]; for (int q = 0; q < queries.size(); q++) { String c = queries.get(q).get(0), d = queries.get(q).get(1); if (!parent.containsKey(c) || !parent.containsKey(d) || !find(c).equals(find(d))) answers[q] = -1.0; else answers[q] = weight.get(c) / weight.get(d); // (c / root) / (d / root) = c / d } return answers; } /** Returns x's root and flattens the path; afterwards weight(x) = x / root. */ private String find(String x) { String p = parent.get(x); if (p.equals(x)) return x; String root = find(p); weight.put(x, weight.get(x) * weight.get(p)); // (x / p) * (p / root) parent.put(x, root); return root; } /** Records a / b = value by hanging a's root under b's root. */ private void union(String a, String b, double value) { for (String s : List.of(a, b)) { parent.putIfAbsent(s, s); weight.putIfAbsent(s, 1.0); } String ra = find(a), rb = find(b); if (ra.equals(rb)) return; parent.put(ra, rb); weight.put(ra, value * weight.get(b) / weight.get(a)); // ra / rb = (a / b) * (b / rb) / (a / ra) }}in the room
How to say it in the interview
talk track
- Say: "Each fact is two weighted edges, a → b with a/b and b → a with b/a. A query is a path, and the answer is the product along it."
- Clarify: unknown variables give -1.0, even for x / x; a known variable over itself gives 1.0.
- Code the DFS per query; complexity O(Q · (V + E)).
- Offer weighted union-find as the follow-up for many queries.
traps
- Forgetting the reverse edge b → a = 1 / value — then b / a can't be answered.
- Returning 1.0 for x / x when x appears in no fact (it must be -1.0).
- No
seenset: the DFS walks a → b → a → … forever. - Sharing one
seenset across all queries — the second query then finds everything already visited. Use a fresh set per query.
what they ask next
Follow-ups
What if the facts could contradict each other?
Weighted union-find catches it: when a and b already share a root, check weight(a) / weight(b) against the new value (within a small epsilon).
10⁵ queries on the same facts?
Build the weighted union-find once; each query is then two finds — near O(1) amortized.
Find the best exchange path (largest product) instead of any path?
That's Path with Maximum Probability: Dijkstra with a max-heap on products (or −log weights).
before you submit
Edge cases to test
- x / x where x is unknown → -1.0; a / a where a is known → 1.0.
- Variables in two separate groups → -1.0 across the groups.
- The query is an equation reversed (b / a) → 1 / value.
- Names are multi-character ("bc", "ab12") — treat them as whole strings, not letters.
practise next
Similar problems
- #1514Path with Maximum ProbabilityMediumin Shortest Paths
- #990Satisfiability of Equality EquationsMediumin Union-Find & MST
- #721Accounts MergeMediumin Union-Find & MST