Evaluate Division
MedPrompt
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.0Example 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, Djconsist of lower case English letters and digits.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach treats the problem as an all-pairs shortest path problem on a graph, but with multiplication as the path combination operator instead of addition. The Floyd-Warshall algorithm is a dynamic programming technique that computes the values of all possible divisions between variables in a single preprocessing step. After this step, any query can be answered in constant time.
Algorithm
- Variable to Index Mapping: Create a mapping from each unique variable string to an integer index (from 0 to
V-1, whereVis the number of unique variables). - Matrix Initialization: Create a
V x Vmatrix, let's call itdist. Initializedist[i][j]to a sentinel value (e.g., -1.0) to represent that the value ofvar_i / var_jis unknown. Initialize the diagonaldist[i][i]to 1.0, asvar_i / var_i = 1. - Populate Direct Edges: Iterate through the input
equations. For each equationA / B = value, leti = index(A)andj = index(B). Setdist[i][j] = valueanddist[j][i] = 1.0 / value. - Floyd-Warshall Execution: Apply the Floyd-Warshall algorithm to fill in the rest of the matrix. The standard algorithm for shortest paths is
dist[i][j] = dist[i][k] + dist[k][j]. We adapt this for division:dist[i][j] = dist[i][k] * dist[k][j]. This is done using three nested loops:for k from 0 to V-1: for i from 0 to V-1: for j from 0 to V-1: if dist[i][k] != -1.0 and dist[k][j] != -1.0: dist[i][j] = dist[i][k] * dist[k][j] - Process Queries: For each query
C / D, find their indicesi = index(C)andj = index(D). The answer isdist[i][j]. If eitherCorDwas not in the original equations, or ifdist[i][j]is still the sentinel value, the answer is -1.0.
Walkthrough
First, we map every unique variable to an integer index to facilitate the use of a 2D array (adjacency matrix). This matrix, dist, will store the results of divisions. We initialize dist[i][i] to 1.0 and populate it with the direct division values from the input equations. For A / B = V, we set dist[idx(A)][idx(B)] = V and dist[idx(B)][idx(A)] = 1/V.
The core of the approach is the Floyd-Warshall algorithm. It systematically considers every variable k as an intermediate in the path between any two other variables i and j. If we know i / k and k / j, we can compute i / j as (i / k) * (k / j). By iterating through all possible i, j, and k, we can fill the entire dist matrix with all derivable division results.
Once the matrix is fully computed, answering a query C / D is a simple lookup in the matrix. If the entry dist[idx(C)][idx(D)] was computed, that's the answer; otherwise, no relationship can be established, and we return -1.0.
import java.util.*; class Solution { public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) { Map<String, Integer> varToIndex = new HashMap<>(); int varCount = 0; for (List<String> eq : equations) { if (!varToIndex.containsKey(eq.get(0))) { varToIndex.put(eq.get(0), varCount++); } if (!varToIndex.containsKey(eq.get(1))) { varToIndex.put(eq.get(1), varCount++); } } double[][] dist = new double[varCount][varCount]; for (int i = 0; i < varCount; i++) { Arrays.fill(dist[i], -1.0); dist[i][i] = 1.0; } for (int i = 0; i < equations.size(); i++) { int u = varToIndex.get(equations.get(i).get(0)); int v = varToIndex.get(equations.get(i).get(1)); dist[u][v] = values[i]; dist[v][u] = 1.0 / values[i]; } for (int k = 0; k < varCount; k++) { for (int i = 0; i < varCount; i++) { for (int j = 0; j < varCount; j++) { if (dist[i][k] != -1.0 && dist[k][j] != -1.0) { dist[i][j] = dist[i][k] * dist[k][j]; } } } } double[] results = new double[queries.size()]; for (int i = 0; i < queries.size(); i++) { List<String> query = queries.get(i); Integer start = varToIndex.get(query.get(0)); Integer end = varToIndex.get(query.get(1)); if (start == null || end == null) { results[i] = -1.0; } else { results[i] = dist[start][end]; } } return results; }}Complexity
Time
O(V^3 + M), where V is the number of unique variables and M is the number of queries. Since V can be at most 2N, the complexity is O(N^3 + M). The V^3 term for the Floyd-Warshall algorithm dominates.
Space
O(V^2) or O(N^2), where V is the number of unique variables and N is the number of equations. This is for storing the V x V distance matrix.
Trade-offs
Pros
Once the preprocessing is done, queries are answered in O(1) time.
The logic is a standard, well-known algorithm, making it relatively straightforward to implement if familiar with it.
Cons
The preprocessing step has a high time complexity of O(N^3), which is inefficient for larger numbers of variables.
It requires O(N^2) space for the adjacency matrix, which can be substantial.
Solutions
Solution
class Solution {private Map<String, String> p;private Map<String, Double> w;public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) { int n = equations.size(); p = new HashMap<>(); w = new HashMap<>(); for (List<String> e : equations) { p.put(e.get(0), e.get(0)); p.put(e.get(1), e.get(1)); w.put(e.get(0), 1.0); w.put(e.get(1), 1.0); } for (int i = 0; i < n; ++i) { List<String> e = equations.get(i); String a = e.get(0), b = e.get(1); String pa = find(a), pb = find(b); if (Objects.equals(pa, pb)) { continue; } p.put(pa, pb); w.put(pa, w.get(b) * values[i] / w.get(a)); } int m = queries.size(); double[] ans = new double[m]; for (int i = 0; i < m; ++i) { String c = queries.get(i).get(0), d = queries.get(i).get(1); ans[i] = !p.containsKey(c) || !p.containsKey(d) || !Objects.equals(find(c), find(d)) ? -1.0 : w.get(c) / w.get(d); } return ans; }private String find(String x) { if (!Objects.equals(p.get(x), x)) { String origin = p.get(x); p.put(x, find(p.get(x))); w.put(x, w.get(x) * w.get(origin)); } return p.get(x); }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.