Evaluate Division
Medium · Graphs · Array · String · Depth-First Search · Breadth-First Search · Union Find · Graph · Shortest Path
Problem
You are given equations and values of the same length: equations[i] = [A, B] together with values[i] = k means A / B = k, where A and B are variable names. You are also given queries, where queries[j] = [C, D] asks for the value of C / D.
Return a list with the answer to each query. If an answer cannot be determined from the equations, including when a variable never appears in any equation, the answer is -1.0.
The equations are consistent, never divide by zero, and every value is positive. Answers are accepted within 10^-5.
Examples
Input: equations = [["x","y"],["y","z"]], values = [4.0,0.5], queries = [["x","z"],["z","x"],["y","w"],["y","y"]] Output: [2.0,0.5,-1.0,1.0]
x/z = 4 · 0.5 = 2, z/x is its reciprocal, w is unknown, and y/y = 1.
Input: equations = [["p","q"]], values = [3.0], queries = [["q","p"],["r","r"]] Output: [0.33333,-1.0]
q/p = 1/3, while r never appears, so even r/r cannot be determined.
Constraints
- 1 <= len(equations) <= 20
- len(equations[i]) == 2
- 1 <= len(A), len(B) <= 5
- len(values) == len(equations) and 0.0 < values[i] <= 20.0
- 1 <= len(queries) <= 20
- Variable names use lowercase English letters and digits
Approaches
- Baseline: search the graph for every query — time O(Q · (V + E)), space O(V + E)
Follow-up
What if equations and queries arrive mixed in one stream? The weighted union-find handles it directly: each equation is a union, each query two finds, so every operation is nearly constant time. A per-query search would redo its walk every time.
Related problems
Start free on Cariara · Coding problems · System design studio
