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.
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 <= 20equations[i].length == 21 <= Ai.length, Bi.length <= 5values.length == equations.length0.0 < values[i] <= 20.01 <= queries.length <= 20queries[i].length == 21 <= Cj.length, Dj.length <= 5Ai, Bi, Cj, Dj consist of lower case English letters and digits.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.
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.
JavaScript
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.
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.
This C++ solution uses a Union-Find data structure with path compression. For each equation, it unifies the variables into a single component, maintaining their relative ratios. For each query, it determines whether the variables are in the same component and calculates the result using the stored weights (which represent ratios to their respective roots).
Java
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.
| Approach | Complexity |
|---|---|
| Graph Representation and DFS | 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. |
| Union-Find with Path Compression | 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. |
Evaluate Division - Leetcode 399 - Python • NeetCodeIO • 41,346 views views
Watch 9 more video solutions →Practice Evaluate Division with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor