[Medium] 399. Evaluate Division

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 = ?.

Return the answers to all queries. If a single answer cannot be determined, return -1.0.

Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.

Examples

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.00000,0.50000,-1.00000,1.00000,-1.00000]
Explanation: 
Given: a / b = 2.0, b / c = 3.0
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
Return: [6.0, 0.5, -1.0, 1.0, -1.0]

Example 2:

Input: equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
Output: [3.75000,0.40000,5.00000,0.20000]

Example 3:

Input: equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
Output: [0.50000,2.00000,-1.00000,-1.00000]

Constraints

• 1 <= equations.length <= 20
• equations[i].length == 2
• 1 <= Ai.length, Bi.length <= 5
• values.length == equations.length
• 0.0 < values[i] <= 20.0
• 1 <= queries.length <= 20
• queries[i].length == 2
• 1 <= Cj.length, Dj.length <= 5
• Ai, Bi, Cj, Dj consist of lower case English letters and digits.

Thinking Process

1. Weighted Union-Find: Maintains ratios relative to root

• Model entities as nodes and relationships as edges.
• Pick traversal (BFS/DFS) or shortest-path (Dijkstra) based on weights.
• Union-Find helps when connectivity updates are frequent.

Common Approaches

Typical techniques for this pattern:

Approach	Time	Space	Notes
Recursive DFS (this problem)	O(n)	O(h) stack	Natural for trees and graphs
Iterative DFS (stack)	O(n)	O(n)	Avoid recursion depth limits
DFS with memoization	O(n)	O(n)	Overlapping subproblems on graphs
Backtracking DFS	O(2^n) typical	O(n)	Enumerate choices with pruning

Solution

Time Complexity: O((E + Q) × α(n)) where E = equations, Q = queries, n = variables
Space Complexity: O(n) - For the union-find structure

This solution uses Union-Find with path compression and union by weight to maintain ratios between variables.

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

    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 (var e : g.get(cur).entrySet()) {
            if (!seen.contains(e.getKey())) {
                double res = dfs(g, e.getKey(), target, prod * e.getValue(), seen);
                if (res != -1.0) return res;
            }
        }
        return -1.0;
    }
}```

### Solution Explanation

**Approach:** Recursive DFS (this problem)

**Key idea:** 1. **Weighted Union-Find**: Maintains ratios relative to root

**How the code works:**
1. **Weighted Union-Find**: Maintains ratios relative to root
- Model entities as nodes and relationships as edges.
- Pick traversal (BFS/DFS) or shortest-path (Dijkstra) based on weights.
- Union-Find helps when connectivity updates are frequent.

**Walkthrough** — input `equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]`, expected output `[6.00000,0.50000,-1.00000,1.00000,-1.00000]`:

Given: a / b = 2.0, b / c = 3.0
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
Return: [6.0, 0.5, -1.0, 1.0, -1.0]

| Solution | Time | Space | Notes |
|----------|------|-------|-------|
| Union-Find | O((E+Q)×α(n)) | O(n) | Optimal for many queries |
| Graph DFS | O(E + Q×V) | O(E+V) | Simple, good for few queries |

### How Solution 1 Works

1. **Union-Find Structure**:
   - `weights[node] = {parent, weight}` where `weight = node / parent`
   - Example: If `a / b = 2.0`, then `weights[a] = {b, 2.0}`

2. **Find with Path Compression**:
   - Finds root and compresses path
   - Updates weight along path: `node_weight = node_weight × parent_weight`
   - Returns `{root, node_weight}`

3. **Union Operation**:
   - Connects two components with a ratio
   - If `a / b = value`, connects roots with appropriate weight
   - Weight formula: `root_weight = (divisor_weight × value) / dividend_weight`

4. **Query Processing**:
   - If both variables exist and have same root, return `dividend_weight / divisor_weight`
   - Otherwise return `-1.0`

### Key Insight

The Union-Find structure maintains ratios relative to the root:
- `weights[node] = {root, node/root}`
- To find `a / b`: If both have same root, `(a/root) / (b/root) = a/b`
## Example Walkthrough

**Input:** `equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"]]`

### Solution 1 (Union-Find):

Step 1: Process “a / b = 2.0” unite(a, b, 2.0): find(a) → {a, 1.0} find(b) → {b, 1.0} weights[a] = {b, 2.0}

Step 2: Process “b / c = 3.0” unite(b, c, 3.0): find(b) → {b, 1.0} find(c) → {c, 1.0} weights[b] = {c, 3.0}

Step 3: Query “a / c = ?” find(a) → find(b) → {c, 1.0} Path: a → b → c weights[a] = {b, 2.0} find(b) → {c, 3.0} weights[a] = {c, 2.0 × 3.0 = 6.0}

find(c) → {c, 1.0}

Result: 6.0 / 1.0 = 6.0

### Solution 2 (Graph DFS):

Graph: a → [(b, 2.0)] b → [(a, 0.5), (c, 3.0)] c → [(b, 0.333)]

Query “a / c”: DFS(a, c): a → b (product = 2.0) b → c (product = 2.0 × 3.0 = 6.0) Found! Return 6.0

### Complexity
| Solution | Time | Space | Notes |
|----------|------|-------|-------|
| Union-Find | O((E+Q)×α(n)) | O(n) | Optimal for many queries |
| Graph DFS | O(E + Q×V) | O(E+V) | Simple, good for few queries |

## Common Mistakes

1. **Variable not in equations**: Return `-1.0`
2. **Same variable query**: `a / a = 1.0`
3. **Disconnected components**: Variables in different components return `-1.0`
4. **Single equation**: Handle minimal input
5. **Transitive relationships**: `a/b=2, b/c=3` → `a/c=6`

1. **Path compression**: Not updating weights during path compression
2. **Union weight calculation**: Wrong formula for connecting roots
3. **Division by zero**: Should not occur per problem constraints
4. **Missing variables**: Not checking if variables exist before querying

## Optimization Tips

1. **Path compression**: Essential for O(α(n)) amortized time
2. **Lazy initialization**: Only create entries when needed
3. **Early termination**: Check if variables exist before processing

## Related Problems

- [990. Satisfiability of Equality Equations](https://leetcode.com/problems/satisfiability-of-equality-equations/) - Similar Union-Find structure
- [547. Number of Provinces](https://leetcode.com/problems/number-of-provinces/) - Union-Find for connectivity
- [684. Redundant Connection](https://leetcode.com/problems/redundant-connection/) - Union-Find for cycle detection

## Pattern Recognition

This problem demonstrates the **"Weighted Union-Find"** pattern:

1. Maintain parent and weight in union-find structure
2. Path compression updates weights along path
3. Union operation connects with correct weight
4. Query uses weight ratio when same root ```

Similar problems:

• Satisfiability of Equality Equations
• Network Connectivity with Weights
• Ratio Queries

  References

• LC 399: Evaluate Division on LeetCode
• LeetCode Discuss — LC 399: Evaluate Division
• LeetCode Editorial (may require premium)

Key Takeaways

1. Weighted Union-Find: Maintains ratios relative to root
2. Path compression: Updates weights along path for efficiency
3. Union by weight: Connects roots with correct ratio
4. Query formula: dividend_weight / divisor_weight when same root