Problem 25.7 · Union-Find (DSU)Medium

Evaluate Division

PatternUnion-Find Graph DFS and Flood Fill

What it teaches: Weighted union-find: each node stores its ratio to its parent, and find multiplies ratios along the way.

Practise it on judges as “Evaluate Division”.

The problem

equations[i] = [a, b] with values[i] means a / b = values[i]. For each query [c, d], return c / d, or −1.0 if it can't be determined.

Example 1

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]

Constraints

1 ≤ equations ≤ 20
Values are positive
No contradictions

Pattern clues in the wording

→ Ratios chained through intermediates

These clues point to Union-Find: Keep each group as a tree with a root; find the root to test membership and link roots to merge groups.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        return new double[queries.size()];
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	equations = [["a","b"],["b","c"]] values = [2,3] queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]	[6,0.5,-1,1,-1]
2	equations = [["a","b"],["b","c"],["bc","cd"]] values = [1.5,2.5,5] queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]	[3.75,0.4,5,0.2]

From slow to fast

Approaches

1. Weighted union-find · O((E + Q) α)2. DFS on a weighted graph · O(Q × (V + E))

Weighted union-find

Time O((E + Q) α) Space O(variables)

find(x) compresses the path and multiplies weights so weight[x] = x / root.

union(a, b, v): with roots ra, rb, set parent[ra] = rb and weight[ra] = v × weight[b] / weight[a] (that is ra / rb).

Approach 1

import java.util.*;

class Solution {
    private final Map<String, String> parent = new HashMap<>();
    private final Map<String, Double> weight = new HashMap<>();

    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        for (int i = 0; i < values.length; i++) {
            String a = equations.get(i).get(0), b = equations.get(i).get(1);
            add(a); add(b);
            String ra = find(a), rb = find(b);
            if (!ra.equals(rb)) {
                parent.put(ra, rb);
                weight.put(ra, values[i] * weight.get(b) / weight.get(a));
            }
        }
        double[] out = new double[queries.size()];
        for (int i = 0; i < out.length; i++) {
            String c = queries.get(i).get(0), d = queries.get(i).get(1);
            if (!parent.containsKey(c) || !parent.containsKey(d) || !find(c).equals(find(d))) out[i] = -1.0;
            else out[i] = weight.get(c) / weight.get(d);
        }
        return out;
    }

    private void add(String x) {
        if (parent.putIfAbsent(x, x) == null) weight.put(x, 1.0);
    }

    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;
    }
}

Verdict: Each query is two finds.

DFS on a weighted graph

Time O(Q × (V + E)) Space O(V + E)

Edges a → b with weight v and b → a with 1 / v. For each query, DFS from c multiplying weights until d is reached.

Approach 2

import java.util.*;

class Solution {
    private final Map<String, Map<String, Double>> g = new HashMap<>();

    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        for (int i = 0; i < values.length; i++) {
            String a = equations.get(i).get(0), b = equations.get(i).get(1);
            g.computeIfAbsent(a, k -> new HashMap<>()).put(b, values[i]);
            g.computeIfAbsent(b, k -> new HashMap<>()).put(a, 1.0 / values[i]);
        }
        double[] out = new double[queries.size()];
        for (int i = 0; i < out.length; i++) {
            String c = queries.get(i).get(0), d = queries.get(i).get(1);
            out[i] = g.containsKey(c) && g.containsKey(d) ? dfs(c, d, new HashSet<>()) : -1.0;
        }
        return out;
    }

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

Verdict: Simpler to reason about; fine for small inputs.

Before you submit

Edge cases and common mistakes

Test these inputs

Unknown variable (−1.0, even x / x)
Query in the reverse direction

Mistakes people make

Returning 1.0 for x / x when x never appeared.

Interview

Follow-up questions

How could you detect contradictory equations?