Evaluate Division

MEDIUM✓ CHIP-TIMEDLC #399 — FULL STATEMENT ↗

The drill: You're given equations like a / b = 2.0 — each one a known ratio between two variables. Given a batch of new division queries, answer every one using only the ratios you were told, chaining them through shared variables where needed. Anything that can't be derived is −1.0.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A batch of equations arrives, each one a known division result between two variables, like a divided by b equals some value. Those equations only ever cover some pairs directly — the task is to answer a separate batch of queries asking for the value of other divisions, chaining through shared variables where a direct answer was never given.

Every equation implies its reverse for free — if a divided by b is known, so is b divided by a, just inverted — and a chain of known ratios through a shared variable can be multiplied together to answer a query nobody stated directly.

When a query involves a variable that never appeared in any equation at all, or asks for a ratio that simply can't be derived through any chain of known values, the answer for that query is −1.0 rather than a guess.

EX 01

equations = [["a", "b"], ["b", "c"]] · values = [2, 3] · queries = [["a", "c"], ["c", "a"], ["a", "e"], ["a", "a"], ["x", "x"]]

→ [6, 0.166667, -1, 1, -1]

A CHAIN OF TWO, ITS REVERSE, AN UNREACHABLE VAR, A SELF-QUERY, AND A VAR NEVER SEEN AT ALL

EX 02

equations = [["a", "b"]] · values = [2] · queries = [["a", "b"], ["b", "a"], ["a", "c"], ["c", "a"]]

→ [2, 0.5, -1, -1]

A SINGLE EQUATION, FORWARD, REVERSE, AND TWO UNREACHABLE QUERIES

EX 03

equations = [["a", "b"], ["b", "c"], ["c", "d"]] · values = [2, 2, 5] · queries = [["a", "d"], ["d", "a"], ["a", "c"], ["b", "d"]]

→ [20, 0.05, 4, 10]

A CHAIN OF THREE, ENDPOINTS AND MIDPOINTS BOTH QUERIED

up to a few hundred equations and queries
equation values are positive numbers
an unknown variable in a query, or an underivable ratio, answers −1.0
answers are checked against a small floating-point tolerance

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

a / b = 2.0 and b / c = 3.0 together tell you a / c, even though nobody ever gave you that ratio directly. What structure connects variables through the ratios linking them?

HINT 2 THE STRUCTURE

Treat every variable as a node and every equation as a weighted, two-way edge — a/b = v also means b/a = 1/v. Answering a query is then finding a path between two nodes and multiplying the weights along it.

HINT 3 ONE STEP FROM THE ANSWER

For a query (x, y), search outward from x for y, multiplying edge weights as you go. If y is never reached — including if x or y never appeared in any equation at all — the answer is −1.0.

COACH'S BOARD — THE PATTERN, STEP BY STEP

DIVISION THROUGH THE UNIONPATTERN · WEIGHTED UNION-FINDa/b = 2, b/c = 3 · queries: a/c, c/a, a/e, a/a, x/x

STEP 1

Three variables chain by division: a/b = 2, b/c = 3. Union-find fuses each equation into a shared root, carrying the ratio along.

STEP 1 / 6 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/evaluate-division.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def calcEquation(
        self, equations: List[List[str]], values: List[int], queries: List[List[str]]
    ) -> List[float]:
        parent = {}
        ratio = {}  # ratio[x] = x / parent[x]

        def find(x):
            if x not in parent:
                parent[x] = x
                ratio[x] = 1.0
                return x, 1.0
            if parent[x] == x:
                return x, 1.0
            root, r = find(parent[x])
            ratio[x] *= r
            parent[x] = root
            return root, ratio[x]

        for (a, b), v in zip(equations, values):
            ra, wa = find(a)  # a = wa * ra
            rb, wb = find(b)  # b = wb * rb
            if ra == rb:
                continue
            # a / b = v  =>  wa*ra / (wb*rb) = v  =>  ra = (v * wb / wa) * rb
            parent[ra] = rb
            ratio[ra] = v * wb / wa

        result = []
        for a, b in queries:
            if a not in parent or b not in parent:
                result.append(-1.0)
                continue
            ra, wa = find(a)
            rb, wb = find(b)
            result.append(wa / wb if ra == rb else -1.0)
        return result

TIME O((V+Q)·Α(V))SPACE O(V)PYTHON · RACE PACE · 37 LN

class Solution:
    def calcEquation(
        self, equations: List[List[str]], values: List[int], queries: List[List[str]]
    ) -> List[float]:
        graph = collections.defaultdict(dict)
        for (a, b), v in zip(equations, values):
            graph[a][b] = float(v)
            graph[b][a] = 1.0 / v

        def dfs(src, dst, visited):
            if src not in graph or dst not in graph:
                return -1.0
            if src == dst:
                return 1.0
            visited.add(src)
            for nxt, weight in graph[src].items():
                if nxt in visited:
                    continue
                sub = dfs(nxt, dst, visited)
                if sub != -1.0:
                    return weight * sub
            return -1.0

        return [dfs(a, b, set()) for a, b in queries]

TIME O(Q·(V+E))SPACE O(V+E)PYTHON · TRAINING PACE · 24 LN

class Solution {
    public double[] calcEquation(String[][] equations, int[] values, String[][] queries) {
        Map<String, String> parent = new HashMap<>();
        Map<String, Double> ratio = new HashMap<>(); // ratio[x] = x / parent[x]

        for (int i = 0; i < equations.length; i++) {
            String a = equations[i][0], b = equations[i][1];
            double v = values[i];
            String ra = find(parent, ratio, a);
            double wa = ratio.get(a);
            String rb = find(parent, ratio, b);
            double wb = ratio.get(b);
            if (ra.equals(rb)) continue;
            // a / b = v  =>  wa*ra / (wb*rb) = v  =>  ra = (v * wb / wa) * rb
            parent.put(ra, rb);
            ratio.put(ra, v * wb / wa);
        }

        double[] out = new double[queries.length];
        for (int i = 0; i < queries.length; i++) {
            String a = queries[i][0], b = queries[i][1];
            if (!parent.containsKey(a) || !parent.containsKey(b)) {
                out[i] = -1.0;
                continue;
            }
            String ra = find(parent, ratio, a);
            double wa = ratio.get(a);
            String rb = find(parent, ratio, b);
            double wb = ratio.get(b);
            out[i] = ra.equals(rb) ? wa / wb : -1.0;
        }
        return out;
    }

    // path-compressing find; ratio.get(x) afterward is x's ratio to the returned root
    private String find(Map<String, String> parent, Map<String, Double> ratio, String x) {
        if (!parent.containsKey(x)) {
            parent.put(x, x);
            ratio.put(x, 1.0);
            return x;
        }
        if (parent.get(x).equals(x)) return x;
        String root = find(parent, ratio, parent.get(x));
        ratio.put(x, ratio.get(x) * ratio.get(parent.get(x)));
        parent.put(x, root);
        return root;
    }
}

TIME O((V+Q)·Α(V))SPACE O(V)JAVA · RACE PACE · 48 LN

class Solution {
    public double[] calcEquation(String[][] equations, int[] values, String[][] queries) {
        Map<String, Map<String, Double>> graph = new HashMap<>();
        for (int i = 0; i < equations.length; i++) {
            String a = equations[i][0], b = equations[i][1];
            double v = values[i];
            graph.computeIfAbsent(a, k -> new HashMap<>()).put(b, v);
            graph.computeIfAbsent(b, k -> new HashMap<>()).put(a, 1.0 / v);
        }

        double[] out = new double[queries.length];
        for (int i = 0; i < queries.length; i++) {
            out[i] = dfs(graph, queries[i][0], queries[i][1], new HashSet<>());
        }
        return out;
    }

    private double dfs(Map<String, Map<String, Double>> graph, String src, String dst, Set<String> visited) {
        if (!graph.containsKey(src) || !graph.containsKey(dst)) return -1.0;
        if (src.equals(dst)) return 1.0;
        visited.add(src);
        for (Map.Entry<String, Double> edge : graph.get(src).entrySet()) {
            if (visited.contains(edge.getKey())) continue;
            double sub = dfs(graph, edge.getKey(), dst, visited);
            if (sub != -1.0) return edge.getValue() * sub;
        }
        return -1.0;
    }
}

TIME O(Q·(V+E))SPACE O(V+E)JAVA · TRAINING PACE · 29 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED