Evaluate Division
Problem
You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single variable. You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj = ?.
known = [["a","b",2.0],["b","c",3.0]], query = "a / c"6.0def evaluate_division(eqs, q):
from collections import defaultdict
adj = defaultdict(list)
for a, b, k in eqs:
adj[a].append((b, k)); adj[b].append((a, 1 / k))
x, y = q
if x not in adj or y not in adj: return -1
if x == y: return 1
seen = {x}
def dfs(u, acc):
if u == y: return acc
for v, w in adj[u]:
if v in seen: continue
seen.add(v)
r = dfs(v, acc * w)
if r != -1: return r
return -1
return dfs(x, 1)function evaluateDivision(eqs, q) {
const adj = new Map();
for (const [a, b, k] of eqs) {
if (!adj.has(a)) adj.set(a, []); if (!adj.has(b)) adj.set(b, []);
adj.get(a).push([b, k]); adj.get(b).push([a, 1 / k]);
}
const [x, y] = q;
if (!adj.has(x) || !adj.has(y)) return -1;
if (x === y) return 1;
const seen = new Set([x]);
function dfs(u, acc) {
if (u === y) return acc;
for (const [v, w] of adj.get(u)) if (!seen.has(v)) {
seen.add(v);
const r = dfs(v, acc * w);
if (r !== -1) return r;
}
return -1;
}
return dfs(x, 1);
}class Solution {
Map<String, List<Object[]>> adj;
Set<String> seen;
String Y;
public double evaluateDivision(String[][] eqs, double[] vals, String x, String y) {
adj = new HashMap<>();
for (int i = 0; i < eqs.length; i++) {
String a = eqs[i][0], b = eqs[i][1]; double k = vals[i];
adj.computeIfAbsent(a, z -> new ArrayList<>()).add(new Object[]{ b, k });
adj.computeIfAbsent(b, z -> new ArrayList<>()).add(new Object[]{ a, 1.0 / k });
}
if (!adj.containsKey(x) || !adj.containsKey(y)) return -1;
if (x.equals(y)) return 1;
seen = new HashSet<>(); seen.add(x);
this.Y = y;
return dfs(x, 1.0);
}
private double dfs(String u, double acc) {
if (u.equals(Y)) return acc;
for (Object[] e : adj.get(u)) {
String v = (String) e[0]; double w = (double) e[1];
if (seen.contains(v)) continue;
seen.add(v);
double r = dfs(v, acc * w);
if (r != -1) return r;
}
return -1;
}
}unordered_map<string, vector<pair<string, double>>> adj_;
unordered_set<string> seen_;
string Y_;
double dfs(string u, double acc) {
if (u == Y_) return acc;
for (auto& [v, w] : adj_[u]) {
if (seen_.count(v)) continue;
seen_.insert(v);
double r = dfs(v, acc * w);
if (r != -1) return r;
}
return -1;
}
double evaluateDivision(vector<vector<string>>& eqs, vector<double>& vals, string x, string y) {
adj_.clear();
for (int i = 0; i < (int)eqs.size(); i++) {
adj_[eqs[i][0]].push_back({eqs[i][1], vals[i]});
adj_[eqs[i][1]].push_back({eqs[i][0], 1.0 / vals[i]});
}
if (!adj_.count(x) || !adj_.count(y)) return -1;
if (x == y) return 1;
seen_.clear(); seen_.insert(x);
Y_ = y;
return dfs(x, 1.0);
}Explanation
Each equation a / b = k is really a relationship we can chain. The trick is to treat variables as nodes in a weighted graph: an edge a → b with weight k, and the reverse edge b → a with weight 1/k.
To answer x / y, we DFS from x looking for y, multiplying edge weights along the way. The running product acc starts at 1, and each step does acc * w. When we land on y, the accumulated product is the answer.
A seen set stops us from looping back into a variable we are already exploring. If a branch dead-ends, we backtrack and try another neighbor. If no path connects x to y (or either variable is unknown), we return -1.
Example: a/b = 2 and b/c = 3, query a / c. From a we take edge to b (acc = 2), then edge to c (acc = 2 × 3 = 6). We reached c, so the answer is 6.
Because division is just multiplying ratios along a path, walking the graph and combining weights gives the correct value for any connected pair.