#399 Evaluate Division - Solution

You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [A_i, B_i] and values[i] represent the equation A_i / B_i = values[i]. Each A_i or B_i is a string that represents a single variable.

You are also given some queries, where queries[j] = [C_j, D_j] represents the j^th query where you must find the answer for C_j / D_j = ?.

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.

Note: The variables that do not occur in the list of equations are undefined, so the answer cannot be determined for them.

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 ]
note: x is undefined => -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 <= A_i.length, B_i.length <= 5
values.length == equations.length
0.0 < values[i] <= 20.0
1 <= queries.length <= 20
queries[i].length == 2
1 <= C_j.length, D_j.length <= 5
A_i, B_i, C_j, D_j consist of lower case English letters and digits.

The key idea in #399 Evaluate Division is to model the given equations as a weighted graph. Each variable represents a node, and an equation like a / b = k forms a directed edge from a to b with weight k, and another from b to a with weight 1/k. Once the graph is built, each query becomes a path-search problem.

You can use Depth-First Search (DFS) or Breadth-First Search (BFS) to traverse the graph and multiply edge weights along the path to compute the result. If a path exists between the two variables, the accumulated product gives the answer; otherwise return -1. Another efficient strategy is Union Find with weighted ratios, which maintains relationships between connected variables and quickly evaluates queries.

Graph traversal typically runs in O(V + E) per query in the worst case, while Union Find offers near constant-time operations with path compression. Space complexity depends mainly on storing the adjacency list or parent mappings.

Approach	Time Complexity	Space Complexity
DFS/BFS Graph Traversal	O(V + E) per query	O(V + E)
Union Find with Weights	O(N + Q * α(N))	O(N)

Solutions (4)

Graph Representation and DFS

Approach: Represent the given variable equations as a graph. Each variable is a node, and an equation between two variables becomes a directed edge with a weight from one node to another representing the ratio. To find the result of a query, search for a path from the dividend node to the divisor node using Depth First Search (DFS). If a path is found, multiply the weights along the path to get the result. If no path is found, return -1.0 as the result cannot be determined.

Time Complexity: O(V + E) for each query, where V is the number of variables and E is the number of equations due to the DFS traversal. Overall complexity is O(Q * (V + E)) for Q queries.
Space Complexity: O(V + E) for storing the graph.

Python JavaScript

1from collections import defaultdict
2
3def calcEquation(equations, values, queries):
4    graph = defaultdict(dict)
5    
6    # Build the graph
7    for (dividend, divisor), value in zip(equations, values):
8        graph[dividend][divisor] = value
9        graph[divisor][dividend] = 1 / value
10    
11    def dfs(start, end, visited, value):
12        if start == end:
13            return value
14        visited.add(start)
15
16        for neighbor, weight in graph[start].items():
17            if neighbor not in visited:
18                result = dfs(neighbor, end, visited, value * weight)
19                if result is not None:
20                    return result
21                
22        return None
23
24    results = []
25    for dividend, divisor in queries:
26        if dividend not in graph or divisor not in graph:
27            results.append(-1.0)
28        else:
29            visited = set()
30            result = dfs(dividend, divisor, visited, 1)
31            results.append(result if result is not None else -1.0)
32
33    return results

Explanation

The Python implementation uses a recursive DFS function to find a path from the start variable to the end variable. The graph is built using a dictionary of dictionaries, allowing easy access to directly connected nodes and the associated division value. If a direct or indirect path exists, the function calculates the result by multiplying the weights along the path. If no path can be found, it returns -1.0.

Union-Find with Path Compression

Approach: Use Union-Find (Disjoint Set Union, DSU) with path compression to represent connected components of variables where each component can efficiently find the "parent" or representative of a set. Each variable is associated with a weight that represents its relative scale with respect to its parent. This method efficiently handles union operations and queries to determine the result by finding the root of each variable and combining their scales.

Time Complexity: O(E + Q * α(V)), where E is the number of equations, Q is the number of queries, V is the number of variables, and α is the inverse Ackermann function, which grows very slowly.
Space Complexity: O(V) for storing parent information and weights.

C++Java

1#include <unordered_map>
2#include <vector>
3#include <string>
4
using namespace std;

class Solution {
public:
    vector<double> calcEquation(
        vector<vector<string>>& equations, 
        vector<double>& values, 
        vector<vector<string>>& queries) {

        unordered_map<string, pair<string, double>> parents;

        // Find function with path compression
        function<pair<string, double>(string)> find = [&](string v) {
            if (!parents.count(v)) return make_pair(v, 1.0);
            auto& [p, w] = parents[v];
            if (v != p) {
                auto result = find(p);
                parents[v] = {result.first, w * result.second};
            }
            return parents[v];
        };

        // Union function
        auto unite = [&](string v1, string v2, double ratio) {
            auto [root1, weight1] = find(v1);
            auto [root2, weight2] = find(v2);
            
            if (root1 != root2) {
                parents[root2] = {root1, ratio * weight1 / weight2};
            }
        };

        for (int i = 0; i < equations.size(); ++i) {
            const auto& eq = equations[i];
            unite(eq[0], eq[1], values[i]);
        }

        vector<double> results;
        for (const auto& query : queries) {
            if (!parents.count(query[0]) || !parents.count(query[1])) {
                results.push_back(-1.0);
                continue;
            }

            auto [root1, weight1] = find(query[0]);
            auto [root2, weight2] = find(query[1]);

            if (root1 != root2) {
                results.push_back(-1.0);
            } else {
                results.push_back(weight1 / weight2);
            }
        }

        return results;
    }
};