Evaluate Division

Medium Graphs Connected Components Original on LeetCode

Evaluate Division is a medium graphs problem solved with the connected components pattern. The best approach, optimal (weighted union-find), runs in O((E + Q) · α(V)) time and O(V) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (dfs per query) up.

Problem

You are given equations of the form A / B = k: equations[i] = [A, B] is a pair of variable names and values[i] is the value of A / B.

For every query queries[j] = [C, D], return the value of C / D derived from the equations. If it cannot be determined (for instance a variable that never appears in any equation), the answer for that query is -1.0.

The equations are consistent and no value is zero. Return the answers in query order.

Examples

Example 1

Input: equations = [["p","q"],["q","r"]], values = [3.0, 4.0], queries = [["p","r"],["r","q"],["q","q"],["p","z"]]
Output: [12.0, 0.25, 1.0, -1.0]
Why: p / r = (p / q) · (q / r) = 3 · 4 = 12, r / q = 1 / 4, q / q = 1, and z never appears so its answer is -1.

Example 2

Input: equations = [["m","n"],["x","y"]], values = [2.0, 5.0], queries = [["m","x"],["y","x"],["n","m"]]
Output: [-1.0, 0.2, 0.5]
Why: m and x live in separate groups, so their ratio is unknown; the other two follow from one equation each.

Example 3

Input: equations = [["ab","cd"]], values = [1.5], queries = [["ef","ef"],["cd","ab"]]
Output: [-1.0, 0.666667]
Why: ef is not a known variable, so even ef / ef is -1. cd / ab = 1 / 1.5.

Constraints

1 <= equations.length <= 5000, values.length == equations.length
1 <= queries.length <= 5000
Each variable name has 1 to 5 lowercase letters or digits.
0.1 <= values[i] <= 10; the equations never contradict each other.
Answers are compared with a relative tolerance of 1e-5.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00

Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

Approach	Time	Space
Brute force (DFS per query)	`O(Q · (V + E))`	`O(V + E)`
Optimal (weighted union-find)	`O((E + Q) · α(V))`	`O(V)`

1Brute force (DFS per query)

TimeO(Q · (V + E))Each of Q queries may explore the whole graph.

SpaceO(V + E)The adjacency map plus the visited set and recursion stack.

Build a weighted graph with both directions of every equation. For each query, run a DFS from the numerator, multiplying weights along the path, until the denominator is reached.

For each equation a / b = v add edges a -> b (v) and b -> a (1 / v).
For a query (x, y): if either is unknown, answer -1; if x == y, answer 1.
Otherwise DFS from x with product 1, carrying product · weight to each unvisited neighbour; return the product on reaching y, or -1.

class Solution {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        Map<String, Map<String, Double>> g = new HashMap<>();
        for (int i = 0; i < equations.size(); i++) {
            String a = equations.get(i).get(0), b = equations.get(i).get(1);
            g.computeIfAbsent(a, x -> new HashMap<>()).put(b, values[i]);
            g.computeIfAbsent(b, x -> new HashMap<>()).put(a, 1.0 / values[i]);
        }
        double[] ans = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            String x = queries.get(i).get(0), y = queries.get(i).get(1);
            if (!g.containsKey(x) || !g.containsKey(y)) ans[i] = -1.0;
            else if (x.equals(y)) ans[i] = 1.0;
            else ans[i] = dfs(g, x, y, 1.0, new HashSet<>());
        }
        return ans;
    }

    private double dfs(Map<String, Map<String, Double>> g, String cur, String target, double prod, Set<String> seen) {
        if (cur.equals(target)) return prod;
        seen.add(cur);
        for (Map.Entry<String, Double> e : g.get(cur).entrySet()) {
            if (seen.contains(e.getKey())) continue;
            double r = dfs(g, e.getKey(), target, prod * e.getValue(), seen);
            if (r != -1.0) return r;
        }
        return -1.0;
    }
}

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        g = {}
        for (a, b), v in zip(equations, values):
            g.setdefault(a, {})[b] = v
            g.setdefault(b, {})[a] = 1.0 / v

        def dfs(cur: str, target: str, prod: float, seen: set) -> float:
            if cur == target:
                return prod
            seen.add(cur)
            for nxt, w in g[cur].items():
                if nxt in seen:
                    continue
                r = dfs(nxt, target, prod * w, seen)
                if r != -1.0:
                    return r
            return -1.0

        ans = []
        for x, y in queries:
            if x not in g or y not in g:
                ans.append(-1.0)
            elif x == y:
                ans.append(1.0)
            else:
                ans.append(dfs(x, y, 1.0, set()))
        return ans

class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        unordered_map<string, unordered_map<string, double>> g;
        for (int i = 0; i < (int)equations.size(); i++) {
            const string& a = equations[i][0];
            const string& b = equations[i][1];
            g[a][b] = values[i];
            g[b][a] = 1.0 / values[i];
        }
        vector<double> ans;
        for (auto& q : queries) {
            const string& x = q[0];
            const string& y = q[1];
            if (!g.count(x) || !g.count(y)) ans.push_back(-1.0);
            else if (x == y) ans.push_back(1.0);
            else {
                unordered_set<string> seen;
                ans.push_back(dfs(g, x, y, 1.0, seen));
            }
        }
        return ans;
    }

private:
    double dfs(unordered_map<string, unordered_map<string, double>>& g, const string& cur, const string& target, double prod, unordered_set<string>& seen) {
        if (cur == target) return prod;
        seen.insert(cur);
        for (auto& e : g[cur]) {
            if (seen.count(e.first)) continue;
            double r = dfs(g, e.first, target, prod * e.second, seen);
            if (r != -1.0) return r;
        }
        return -1.0;
    }
};

function calcEquation(equations, values, queries) {
    const g = new Map();
    for (let i = 0; i < equations.length; i++) {
        const [a, b] = equations[i];
        if (!g.has(a)) g.set(a, new Map());
        if (!g.has(b)) g.set(b, new Map());
        g.get(a).set(b, values[i]);
        g.get(b).set(a, 1.0 / values[i]);
    }
    function dfs(cur, target, prod, seen) {
        if (cur === target) return prod;
        seen.add(cur);
        for (const [nxt, w] of g.get(cur)) {
            if (seen.has(nxt)) continue;
            const r = dfs(nxt, target, prod * w, seen);
            if (r !== -1.0) return r;
        }
        return -1.0;
    }
    return queries.map(([x, y]) => {
        if (!g.has(x) || !g.has(y)) return -1.0;
        if (x === y) return 1.0;
        return dfs(x, y, 1.0, new Set());
    });
}

2Optimal (weighted union-find)

TimeO((E + Q) · α(V))Each union and query does two finds, nearly O(1) with path compression and union by size.

SpaceO(V)Parent, weight and size arrays plus the name-to-index map.

Give every variable a parent and a weight w[x] = x / parent(x). find follows parents to the root while multiplying weights, then compresses the path so w[x] becomes x / root. For a / b = v, link the two roots with the weight that keeps both ratios consistent. A query x / y in the same group is w[x] / w[y].

Map each variable name to an index; parent[i] = i, w[i] = 1, size[i] = 1.
find(x): if parent[x] != x, r = find(parent[x]); w[x] *= w[parent[x]]; parent[x] = r. Return parent[x].
union(a, b, v): ra = find(a), rb = find(b). If different, attach the smaller root under the larger: ra under rb gets w[ra] = v · w[b] / w[a]; rb under ra gets w[rb] = w[a] / (v · w[b]).
Query (x, y): unknown name -> -1; different roots -> -1; else w[x] / w[y].

class Solution {
    private int[] parent, size;
    private double[] w;

    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();
        parent = new int[n];
        size = new int[n];
        w = new double[n];
        for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; w[i] = 1.0; }
        for (int i = 0; i < equations.size(); i++)
            union(id.get(equations.get(i).get(0)), id.get(equations.get(i).get(1)), values[i]);
        double[] ans = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            Integer x = id.get(queries.get(i).get(0)), y = id.get(queries.get(i).get(1));
            if (x == null || y == null || find(x) != find(y)) ans[i] = -1.0;
            else ans[i] = w[x] / w[y];
        }
        return ans;
    }

    private int find(int x) {
        if (parent[x] != x) {
            int p = parent[x];
            int r = find(p);
            w[x] *= w[p];
            parent[x] = r;
        }
        return parent[x];
    }

    private void union(int a, int b, double v) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return;
        if (size[ra] <= size[rb]) {
            parent[ra] = rb;
            w[ra] = v * w[b] / w[a];
            size[rb] += size[ra];
        } else {
            parent[rb] = ra;
            w[rb] = w[a] / (v * w[b]);
            size[ra] += size[rb];
        }
    }
}

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        ids = {}
        for e in equations:
            for s in e:
                if s not in ids:
                    ids[s] = len(ids)
        n = len(ids)
        parent = list(range(n))
        size = [1] * n
        w = [1.0] * n

        def find(x: int) -> int:
            if parent[x] != x:
                p = parent[x]
                r = find(p)
                w[x] *= w[p]
                parent[x] = r
            return parent[x]

        for (a, b), v in zip(equations, values):
            ia, ib = ids[a], ids[b]
            ra, rb = find(ia), find(ib)
            if ra == rb:
                continue
            if size[ra] <= size[rb]:
                parent[ra] = rb
                w[ra] = v * w[ib] / w[ia]
                size[rb] += size[ra]
            else:
                parent[rb] = ra
                w[rb] = w[ia] / (v * w[ib])
                size[ra] += size[rb]

        ans = []
        for x, y in queries:
            if x not in ids or y not in ids:
                ans.append(-1.0)
                continue
            ix, iy = ids[x], ids[y]
            if find(ix) != find(iy):
                ans.append(-1.0)
            else:
                ans.append(w[ix] / w[iy])
        return ans

class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        unordered_map<string, int> id;
        for (auto& e : equations)
            for (auto& s : e)
                if (!id.count(s)) { int k = id.size(); id[s] = k; }
        int n = id.size();
        parent.assign(n, 0);
        sz.assign(n, 1);
        w.assign(n, 1.0);
        for (int i = 0; i < n; i++) parent[i] = i;
        for (int i = 0; i < (int)equations.size(); i++)
            unite(id[equations[i][0]], id[equations[i][1]], values[i]);
        vector<double> ans;
        for (auto& q : queries) {
            auto ix = id.find(q[0]), iy = id.find(q[1]);
            if (ix == id.end() || iy == id.end() || find(ix->second) != find(iy->second)) ans.push_back(-1.0);
            else ans.push_back(w[ix->second] / w[iy->second]);
        }
        return ans;
    }

private:
    vector<int> parent, sz;
    vector<double> w;

    int find(int x) {
        if (parent[x] != x) {
            int p = parent[x];
            int r = find(p);
            w[x] *= w[p];
            parent[x] = r;
        }
        return parent[x];
    }

    void unite(int a, int b, double v) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return;
        if (sz[ra] <= sz[rb]) {
            parent[ra] = rb;
            w[ra] = v * w[b] / w[a];
            sz[rb] += sz[ra];
        } else {
            parent[rb] = ra;
            w[rb] = w[a] / (v * w[b]);
            sz[ra] += sz[rb];
        }
    }
};

function calcEquation(equations, values, queries) {
    const id = new Map();
    for (const e of equations)
        for (const s of e) if (!id.has(s)) id.set(s, id.size);
    const n = id.size;
    const parent = Array.from({ length: n }, (_, i) => i);
    const size = new Array(n).fill(1);
    const w = new Array(n).fill(1.0);
    function find(x) {
        if (parent[x] !== x) {
            const p = parent[x];
            const r = find(p);
            w[x] *= w[p];
            parent[x] = r;
        }
        return parent[x];
    }
    for (let i = 0; i < equations.length; i++) {
        const a = id.get(equations[i][0]), b = id.get(equations[i][1]), v = values[i];
        const ra = find(a), rb = find(b);
        if (ra === rb) continue;
        if (size[ra] <= size[rb]) {
            parent[ra] = rb;
            w[ra] = v * w[b] / w[a];
            size[rb] += size[ra];
        } else {
            parent[rb] = ra;
            w[rb] = w[a] / (v * w[b]);
            size[ra] += size[rb];
        }
    }
    return queries.map(([qx, qy]) => {
        if (!id.has(qx) || !id.has(qy)) return -1.0;
        const x = id.get(qx), y = id.get(qy);
        if (find(x) !== find(y)) return -1.0;
        return w[x] / w[y];
    });
}

Edge cases to test

A query on an unknown variable, including x / x (answer -1)
A query on a known variable divided by itself (answer 1)
Two variables in different connected groups (answer -1)
The reverse of a given equation (answer 1 / value)

Hints

Hint 1

Draw each variable as a node. a / b = v gives an edge a -> b with weight v and an edge b -> a with weight 1 / v.

Hint 2

A query a / c is the product of the weights along any path from a to c.

Hint 3

To answer many queries fast, store for each variable its ratio to a group representative (weighted union-find).

FAQ

What is the best time complexity for Evaluate Division?

Optimal (weighted union-find) runs in O((E + Q) · α(V)) time and O(V) extra space. Each union and query does two finds, nearly O(1) with path compression and union by size.

Which pattern does Evaluate Division use?

It is a graphs problem that uses the connected components pattern. Other problems with the same pattern: Number of Provinces, Number of Islands.

Is there a brute force solution for Evaluate Division?

Yes. Brute force (DFS per query) takes O(Q · (V + E)) time and O(V + E) space. Build a weighted graph with both directions of every equation.

Which edge cases should I test for Evaluate Division?

A query on an unknown variable, including x / x (answer -1); A query on a known variable divided by itself (answer 1); Two variables in different connected groups (answer -1); The reverse of a given equation (answer 1 / value).