Watch 10 video solutions for Evaluate Division, a medium level problem involving Array, String, Depth-First Search. This walkthrough by NeetCodeIO has 59,147 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.Problem Overview: You receive equations like a / b = 2.0 and must answer queries such as a / c. If the relationships exist through other variables, compute the result using those connections. If no path exists between two variables, return -1.0.
Approach 1: Graph Representation and DFS/BFS (Time: O(Q * (V + E)), Space: O(V + E))
Model the equations as a weighted graph. Each variable becomes a node, and every equation a / b = k creates two edges: a → b with weight k and b → a with weight 1/k. To answer a query like x / y, run a Depth-First Search or Breadth-First Search starting from x. Multiply edge weights along the path until you reach y. If a path exists, the product of weights gives the answer; otherwise return -1.0.
This approach works because ratios compose multiplicatively along paths in the graph. During traversal, maintain a visited set to avoid cycles. DFS is commonly used because the graph is usually small, but BFS works equally well. Building the adjacency list takes O(E) time where E is the number of equations, and each query may traverse the graph once.
Problems like this are classic graph traversal tasks and commonly appear alongside Depth-First Search interview questions.
Approach 2: Union-Find with Path Compression (Time: ~O((E + Q) α(N)), Space: O(N))
Another approach treats each variable as part of a disjoint set. Instead of storing only connectivity, store a weight representing the ratio between a node and its parent. When processing an equation a / b = k, union the sets while preserving the ratio relationship. The parent links maintain multiplicative weights so any node can compute its value relative to the set root.
When answering a query x / y, check whether both variables share the same root. If they do, compute the ratio using their stored weights relative to that root. If they belong to different sets, the relationship is undefined and the answer is -1.0. Path compression keeps the structure shallow and maintains correct weight adjustments.
This weighted Union-Find technique is common in problems involving relative relationships or ratios. It combines Union-Find with algebraic weight propagation to answer queries efficiently.
Recommended for interviews: Start with the graph + DFS explanation because it directly models the problem and demonstrates strong understanding of graph traversal. Many candidates implement this first. The Union-Find approach is more advanced and often viewed as the optimized design because it handles multiple queries efficiently with near-constant time operations.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Graph + DFS | O(Q * (V + E)) | O(V + E) | General solution; easy to implement and ideal when query count is small |
| Graph + BFS | O(Q * (V + E)) | O(V + E) | Preferred when iterative traversal is easier than recursion |
| Union-Find with Weights | O((E + Q) α(N)) | O(N) | Best when many queries must be answered after building relationships |