Problem

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.

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

Examples

Example 1:

1
2
3
4
5
6
7
8
9

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:

1
2
3
4

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:

1
2
3
4

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]

Solution

This problem can be solved using graph traversal techniques.

Method 1 - DFS

  1. Representation as a Graph:
    • Each variable represents a node.
    • For each equation Ai / Bi = values[i], we create a directed edge from Ai to Bi with a weight of values[i] and another edge from Bi to Ai with a weight of 1 / values[i].
  2. Handling Queries:
    • For each query Cj / Dj = ?, we traverse the graph using Depth-First Search (DFS) or Breadth-First Search (BFS) to determine whether there is a path from Cj to Dj.
    • During the traversal, we multiply the weights along the path to compute the result.
  3. Special Cases:
    • If either Cj or Dj is not in the graph, or if there is no path between the two nodes, return -1.0.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

class Solution {
    public double[] calcEquation(
        List<List<String>> equations, 
        double[] values, 
        List<List<String>> queries
    ) {
        // Build graph
        Map<String, Map<String, Double>> 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);
            double val = values[i];
            
            graph.computeIfAbsent(a, k -> new HashMap<>()).put(b, val);
            graph.computeIfAbsent(b, k -> new HashMap<>()).put(a, 1.0 / val);
        }
        
        // DFS helper function to find the result of a/b
        private double dfs(String node, String target, Set<String> visited, double acc) {
            if (!graph.containsKey(node) || !graph.containsKey(target)) 
                return -1.0;
            if (node.equals(target)) 
                return acc;
            
            visited.add(node);
            for (Map.Entry<String, Double> entry : graph.get(node).entrySet()) {
                if (!visited.contains(entry.getKey())) {
                    double res = dfs(entry.getKey(), target, visited, acc * entry.getValue());
                    if (res != -1.0) 
                        return res;
                }
            }
            visited.remove(node);
            return -1.0;
        }
        
        // Handle each query
        double[] ans = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            String c = queries.get(i).get(0);
            String d = queries.get(i).get(1);
            ans[i] = dfs(c, d, new HashSet<>(), 1.0);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class Solution:
    def calcEquation(
        self, 
        equations: List[List[str]], 
        values: List[float], 
        queries: List[List[str]]
    ) -> List[float]:
        # Build graph
        graph: Dict[str, Dict[str, float]] = {}
        for (a, b), val in zip(equations, values):
            if a not in graph:
                graph[a] = {}
            if b not in graph:
                graph[b] = {}
            graph[a][b] = val
            graph[b][a] = 1 / val
        
        # DFS helper function to find the result of a/b
        def dfs(node: str, target: str, visited: set, acc: float) -> float:
            if node not in graph or target not in graph: 
                return -1.0
            if node == target: 
                return acc
            visited.add(node)
            for nei, weight in graph[node].items():
                if nei not in visited:
                    res = dfs(nei, target, visited, acc * weight)
                    if res != -1.0:
                        return res
            visited.remove(node)
            return -1.0
        
        # Handle each query
        ans: List[float] = []
        for c, d in queries:
            ans.append(dfs(c, d, set(), 1.0))
        return ans

Complexity

  • Time: O(V + E * Q), where V is the number of variables, E is the number of edges (equations), and Q is the number of queries.
  • Space: O(V + E) for storing the graph.