Evaluate Division

NeetCode: Evaluate Division · LeetCode: 399. Evaluate Division · Difficulty: Medium

You are given equations A / B = k as pairs of variable names (a List<List<String>>) with a value for each (a double[]), and queries C / D as pairs of names. Return a double[] with one answer per query. Return the answer to each query, or -1.0 if it cannot be determined (an unknown variable, or two variables not connected by any chain of equations). Values are positive and there is no contradiction between equations.

Example

Text

Input:  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]

Treat each variable as a node. The equation a / b = k gives an edge a -> b with weight k and a reverse edge b -> a with weight 1 / k. The answer to x / y is the product of weights along any path from x to y, because the intermediate variables cancel: (a/b) * (b/c) = a/c.

Brute force: DFS per query on a weighted graph

Store the graph as a HashMap from a variable to its list of Edge objects (a neighbour and a weight). For a query, if either variable is unknown return -1.0; if they are equal return 1.0; otherwise run a DFS from the numerator, multiplying weights along the way, until the denominator is reached. The search returns -1.0 when it finds no path. This works as a sentinel because every value is positive, so every real product is positive. Compare the names with equals, not ==.

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Locale;
import java.util.Map;
import java.util.Set;

public class Main {
    static class Solution {
        private static class Edge {
            final String to;
            final double weight;

            Edge(String to, double weight) {
                this.to = to;
                this.weight = weight;
            }
        }

        // Product of edge weights along a path from cur to target, or -1.0 if there is none.
        // Every real answer is positive, so -1.0 cannot be confused with a product.
        private double dfs(Map<String, List<Edge>> graph, String cur, String target, double acc, Set<String> seen) {
            if (cur.equals(target)) {
                return acc;
            }
            seen.add(cur);
            for (Edge e : graph.get(cur)) {
                if (!seen.contains(e.to)) {
                    double ans = dfs(graph, e.to, target, acc * e.weight, seen);
                    if (ans != -1.0) {
                        return ans;
                    }
                }
            }
            return -1.0;
        }

        public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
            Map<String, List<Edge>> graph = new HashMap<>();
            for (int i = 0; i < equations.size(); i++) {
                String a = equations.get(i).get(0);
                String b = equations.get(i).get(1);
                graph.computeIfAbsent(a, k -> new ArrayList<>()).add(new Edge(b, values[i]));
                graph.computeIfAbsent(b, k -> new ArrayList<>()).add(new Edge(a, 1.0 / values[i]));
            }
            double[] result = new double[queries.size()];
            for (int i = 0; i < queries.size(); i++) {
                String x = queries.get(i).get(0);
                String y = queries.get(i).get(1);
                if (!graph.containsKey(x) || !graph.containsKey(y)) {
                    result[i] = -1.0;
                } else {
                    result[i] = dfs(graph, x, y, 1.0, new HashSet<>());
                }
            }
            return result;
        }
    }

    // Builds the list of pairs from a flat list of names: {"a", "b", "b", "c"} gives [[a, b], [b, c]].
    static List<List<String>> pairs(String... names) {
        List<List<String>> out = new ArrayList<>();
        for (int i = 0; i < names.length; i += 2) {
            out.add(List.of(names[i], names[i + 1]));
        }
        return out;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        List<List<String>> equations = pairs("a", "b", "b", "c");
        double[] values = {2.0, 3.0};
        List<List<String>> queries = pairs("a", "c", "b", "a", "a", "e", "a", "a", "x", "x");
        for (double r : s.calcEquation(equations, values, queries)) {
            System.out.println(String.format(Locale.ROOT, "%.5f", r));
        }
        System.out.println(Arrays.toString(s.calcEquation(pairs(), new double[0], pairs("a", "b"))));
    }
}

Output

6.00000
0.50000
-1.00000
1.00000
-1.00000
[-1.0]

The examples print each answer with %.5f. Each query can traverse the whole graph. With V variables, E equations and Q queries: Time: O(Q * (V + E)). Space: O(V + E) for the graph and the visited set.

Optimal: weighted union-find

Keep, for every variable x, a parent and a weight w[x] = x / parent[x]. find returns the root and compresses the path so that w[x] becomes x / root.

To add a / b = k, find the roots ra and rb. If they differ, attach ra under rb with weight w[ra] = k * w[b] / w[a]. This is the value that makes both routes to rb agree: a / rb = (a / b) * (b / rb) = k * w[b] and a / rb = (a / ra) * (ra / rb) = w[a] * w[ra].

Once every variable in a component points to the same root, x / y = (x / root) / (y / root) = w[x] / w[y]. Variables in different components have no known ratio, so the answer is -1.0.

Trace for a/b = 2, b/c = 3: after the first equation parent[a] = b, w[a] = 2. For the second, ra = b, rb = c, so parent[b] = c, w[b] = 3. Query a/c: find(a) sets w[a] = 2 * 3 = 6 with root c, and w[c] = 1, so the answer is 6 / 1 = 6. Query b/a is 3 / 6 = 0.5. The double arithmetic here is exact for these values; in general the results are floating-point approximations, which is why LeetCode accepts answers within a small tolerance.

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Locale;
import java.util.Map;

public class Main {
    static class Solution {
        private int[] parent;
        private double[] weight; // weight[x] = x / parent[x]

        // Returns the root of x and sets weight[x] = x / root (path compression).
        private int find(int x) {
            if (parent[x] == x) {
                return x;
            }
            int p = parent[x];
            int root = find(p);
            // after find(p): weight[p] = p / root, so x / root = (x / p) * (p / root)
            weight[x] *= weight[p];
            parent[x] = root;
            return root;
        }

        // Records a / b = k.
        private void union(int a, int b, double k) {
            int ra = find(a);
            int rb = find(b);
            if (ra != rb) {
                parent[ra] = rb;
                weight[ra] = k * weight[b] / weight[a];
            }
        }

        public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
            Map<String, Integer> id = new HashMap<>();
            for (List<String> eq : equations) {
                for (String name : eq) {
                    if (!id.containsKey(name)) {
                        id.put(name, id.size());
                    }
                }
            }
            parent = new int[id.size()];
            weight = new double[id.size()];
            for (int i = 0; i < parent.length; i++) {
                parent[i] = i;
                weight[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[] result = new double[queries.size()];
            for (int q = 0; q < queries.size(); q++) {
                Integer i = id.get(queries.get(q).get(0));
                Integer j = id.get(queries.get(q).get(1));
                if (i == null || j == null || find(i) != find(j)) {
                    result[q] = -1.0;
                } else {
                    result[q] = weight[i] / weight[j];
                }
            }
            return result;
        }
    }

    // Builds the list of pairs from a flat list of names: {"a", "b", "b", "c"} gives [[a, b], [b, c]].
    static List<List<String>> pairs(String... names) {
        List<List<String>> out = new ArrayList<>();
        for (int i = 0; i < names.length; i += 2) {
            out.add(List.of(names[i], names[i + 1]));
        }
        return out;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        List<List<String>> equations = pairs("a", "b", "b", "c");
        double[] values = {2.0, 3.0};
        List<List<String>> queries = pairs("a", "c", "b", "a", "a", "e", "a", "a", "x", "x");
        for (double r : s.calcEquation(equations, values, queries)) {
            System.out.println(String.format(Locale.ROOT, "%.5f", r));
        }
        System.out.println(Arrays.toString(s.calcEquation(pairs(), new double[0], pairs("a", "b"))));
    }
}

Output

6.00000
0.50000
-1.00000
1.00000
-1.00000
[-1.0]

An unknown x gives x / x = -1.0 (the id.get call returns null), while a known a / a gives 1.0. Time: O((E + Q) * alpha(V)) amortised with path compression (plus hashing the names). Space: O(V).

Edge cases

A variable that appears in no equation: the answer is -1.0, even for x / x.
A known variable divided by itself: 1.0.
Variables in separate components: -1.0.
No equations at all: every query is -1.0.

How to explain it in an interview

Each equation a / b = k is a weighted edge a -> b of weight k plus a reverse edge of weight 1 / k; a query is the product of weights along a path.
DFS or BFS per query is correct and costs O(V + E) per query.
Weighted union-find stores each variable's ratio to its parent; path compression makes it the ratio to the root.
Union sets the root's weight so both routes to the new root agree.
A query is w[x] / w[y] when the roots match, otherwise -1.0; total time is near O((E + Q) * alpha(V)).