# Evaluate Division **Difficulty:** MEDIUM [External](https://leetcode.com/problems/evaluate-division) Canonical: https://scaleengineer.com/dsa/problems/evaluate-division **Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Union Find](https://scaleengineer.com/algorithms/union-find), [Shortest Path](https://scaleengineer.com/algorithms/shortest-path) **Data structures:** Array, String, Graph **Companies:** [Snowflake](https://scaleengineer.com/companies/snowflake), [MakeMyTrip](https://scaleengineer.com/companies/makemytrip), [Zeta](https://scaleengineer.com/companies/zeta), [Citadel](https://scaleengineer.com/companies/citadel), [Rippling](https://scaleengineer.com/companies/rippling), [Snap](https://scaleengineer.com/companies/snap), [BlackRock](https://scaleengineer.com/companies/blackrock), [PhonePe](https://scaleengineer.com/companies/phonepe), [Jane Street](https://scaleengineer.com/companies/jane-street), [GE Healthcare](https://scaleengineer.com/companies/ge-healthcare), [Coinbase](https://scaleengineer.com/companies/coinbase), [Nuro](https://scaleengineer.com/companies/nuro), [Stripe](https://scaleengineer.com/companies/stripe) --- ## 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. **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 <= 20` * `equations[i].length == 2` * `1 <= Ai.length, Bi.length <= 5` * `values.length == equations.length` * `0.0 < values[i] <= 20.0` * `1 <= queries.length <= 20` * `queries[i].length == 2` * `1 <= Cj.length, Dj.length <= 5` * `Ai, Bi, Cj, Dj` consist of lower case English letters and digits. # Approaches ## Floyd-Warshall Algorithm 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. **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. **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. ### Explanation 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. ```java import java.util.*; class Solution { public double[] calcEquation(List> equations, double[] values, List> queries) { Map varToIndex = new HashMap<>(); int varCount = 0; for (List 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 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; } } ``` ### Algorithm 1. **Variable to Index Mapping**: Create a mapping from each unique variable string to an integer index (from 0 to `V-1`, where `V` is the number of unique variables). 2. **Matrix Initialization**: Create a `V x V` matrix, let's call it `dist`. Initialize `dist[i][j]` to a sentinel value (e.g., -1.0) to represent that the value of `var_i / var_j` is unknown. Initialize the diagonal `dist[i][i]` to 1.0, as `var_i / var_i = 1`. 3. **Populate Direct Edges**: Iterate through the input `equations`. For each equation `A / B = value`, let `i = index(A)` and `j = index(B)`. Set `dist[i][j] = value` and `dist[j][i] = 1.0 / value`. 4. **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] ``` 5. **Process Queries**: For each query `C / D`, find their indices `i = index(C)` and `j = index(D)`. The answer is `dist[i][j]`. If either `C` or `D` was not in the original equations, or if `dist[i][j]` is still the sentinel value, the answer is -1.0. ## Graph Traversal with DFS This approach models the problem as a graph, where variables are nodes and an equation `A / B = V` represents a weighted directed edge from `A` to `B` with weight `V` (and an inverse edge from `B` to `A` with weight `1/V`). To evaluate a query `C / D`, we simply need to find a path from node `C` to node `D` in the graph. The result of the division is the product of the weights of the edges along this path. A graph traversal algorithm like Depth-First Search (DFS) or Breadth-First Search (BFS) is perfect for this task. **Time:** O(M * (V + E)), where M is the number of queries. For each query, we might traverse the entire component of the graph. Since V <= 2N and E = 2N, this simplifies to O(M * N). · **Space:** O(V + E) or O(N), where V is the number of variables and E is the number of equations. This space is used for the adjacency list and the recursion stack/visited set during DFS. **Pros:** More efficient in terms of time and space than the Floyd-Warshall approach for the given problem constraints.; Conceptually simple, relying on a standard graph traversal algorithm.; Handles disconnected components naturally. **Cons:** Pathfinding is repeated for each query. If multiple queries share common subpaths, the work is re-done every time.; For a dense graph, its performance can degrade, although for the given constraints, it's efficient enough. ### Explanation We begin by constructing a graph from the given equations. An adjacency list is a suitable representation, implemented using a map of maps (`Map>`). This structure allows us to quickly access the neighbors of any variable and the corresponding division value. For each query `[C, D]`, we initiate a search (e.g., DFS) from the starting node `C`. The search explores the graph, keeping track of the cumulative product of edge weights from `C` to the current node. We also use a `visited` set for each query to avoid getting stuck in cycles and redundant computations. If the search successfully reaches the target node `D`, the final accumulated product is our answer. If `C` or `D` don't exist in our graph, or if the search completes without reaching `D`, it means a value cannot be determined, and we return -1.0. ```java import java.util.*; class Solution { public double[] calcEquation(List> equations, double[] values, List> queries) { Map> graph = buildGraph(equations, values); double[] results = new double[queries.size()]; for (int i = 0; i < queries.size(); i++) { List query = queries.get(i); String start = query.get(0); String end = query.get(1); results[i] = dfs(start, end, new HashSet<>(), graph); } return results; } private Map> buildGraph(List> equations, double[] values) { Map> graph = new HashMap<>(); for (int i = 0; i < equations.size(); i++) { String u = equations.get(i).get(0); String v = equations.get(i).get(1); graph.computeIfAbsent(u, k -> new HashMap<>()).put(v, values[i]); graph.computeIfAbsent(v, k -> new HashMap<>()).put(u, 1.0 / values[i]); } return graph; } private double dfs(String start, String end, Set visited, Map> graph) { if (!graph.containsKey(start) || !graph.containsKey(end)) { return -1.0; } if (start.equals(end)) { return 1.0; } visited.add(start); Map neighbors = graph.get(start); for (Map.Entry neighbor : neighbors.entrySet()) { String nextNode = neighbor.getKey(); if (!visited.contains(nextNode)) { double result = dfs(nextNode, end, visited, graph); if (result != -1.0) { return neighbor.getValue() * result; } } } return -1.0; } } ``` ### Algorithm 1. **Graph Representation**: Use a `HashMap` to build an adjacency list representation of the graph. The map's key is a variable (String), and its value is another map where keys are adjacent variables and values are the division results (edge weights). `Map> graph` 2. **Graph Construction**: Iterate through the `equations` and `values`. For each equation `A / B = V`, add a directed edge from `A` to `B` with weight `V`, and an edge from `B` to `A` with weight `1/V`. 3. **Query Processing via DFS**: For each query `C / D`, perform a Depth-First Search (DFS) starting from node `C` to find a path to node `D`. 4. **DFS Helper Function**: The DFS function, say `dfs(current, target, product, visited)`, will need: * `current`: The current node in the traversal. * `target`: The destination node of the query. * `product`: The accumulated product of weights along the path from the start node to the `current` node. * `visited`: A `Set` to keep track of visited nodes in the current traversal to prevent infinite loops in case of cycles. 5. **DFS Logic**: * If `current` or `target` is not in the graph, return -1.0. * If `current` equals `target`, a path is found; return the accumulated `product`. * Mark `current` as visited. * For each `neighbor` of `current` with edge weight `w`: * Recursively call `dfs(neighbor, target, product * w, visited)`. * If the recursive call returns a value other than -1.0, it means a path was found, so return that value immediately. * If the loop finishes without finding the target, no path exists from `current`. Return -1.0. ## Union-Find with Weights The most efficient approach uses a Disjoint Set Union (DSU) data structure, also known as Union-Find, augmented with weights. This method groups connected variables into sets. For each set, we maintain a relationship between every variable and a single representative 'root' variable. Specifically, for any variable `X` in a set with root `R`, we can find the value of `X / R`. A query `C / D` can then be answered by finding the roots for `C` and `D`. If they share the same root `R`, the answer is `(C / R) / (D / R)`. **Time:** O((N + M) * α(V)), where N is the number of equations, M is the number of queries, V is the number of variables, and α is the very slow-growing inverse Ackermann function. The complexity is amortized and is practically linear. · **Space:** O(V) or O(N), where V is the number of unique variables. This space is for the `parent` and `weight` maps. **Pros:** Extremely fast, with a nearly linear time complexity, making it the most efficient solution.; Processes both the initial equations and the subsequent queries very quickly.; Space efficient, requiring only O(N) space. **Cons:** The implementation is more complex than a standard DFS, particularly the logic for updating weights during path compression in the `find` operation. ### Explanation We use two hashmaps: `parent` to track the parent of each variable and `weight` to store the value of `variable / parent[variable]`. The core of the algorithm lies in the `find` and `union` operations. The `find(i)` operation not only finds the root of the set containing `i` but also performs path compression. As it traverses up to the root, it makes each node a direct child of the root. Crucially, it also updates the `weight` of each node in the path to represent its value divided by the new parent (the root). This ensures that after `find(i)`, `weight[i]` equals `i / root`. The `union(i, j, value)` operation merges the sets of `i` and `j` using the information `i / j = value`. It finds the roots and weights for both `i` and `j` and then links one root to the other, calculating the weight of the new link to maintain consistency. After processing all equations with `union`, we can answer queries. For a query `C / D`, we call `find` on both. If they belong to different sets (different roots), their ratio is unknown. If they share a root, the answer is simply the ratio of their weights relative to the common root. ```java import java.util.*; class Solution { public double[] calcEquation(List> equations, double[] values, List> queries) { Map parent = new HashMap<>(); Map weight = new HashMap<>(); // Initialize parent and weight for all variables for (List eq : equations) { String u = eq.get(0); String v = eq.get(1); parent.put(u, u); parent.put(v, v); weight.put(u, 1.0); weight.put(v, 1.0); } // Process equations with union operation for (int i = 0; i < equations.size(); i++) { String u = equations.get(i).get(0); String v = equations.get(i).get(1); union(u, v, values[i], parent, weight); } // Process queries double[] results = new double[queries.size()]; for (int i = 0; i < queries.size(); i++) { String u = queries.get(i).get(0); String v = queries.get(i).get(1); if (!parent.containsKey(u) || !parent.containsKey(v)) { results[i] = -1.0; continue; } Pair rootU = find(u, parent, weight); Pair rootV = find(v, parent, weight); if (rootU.getKey().equals(rootV.getKey())) { results[i] = rootU.getValue() / rootV.getValue(); } else { results[i] = -1.0; } } return results; } // find operation with path compression and weight update private Pair find(String s, Map parent, Map weight) { if (!s.equals(parent.get(s))) { Pair rootInfo = find(parent.get(s), parent, weight); parent.put(s, rootInfo.getKey()); weight.put(s, weight.get(s) * rootInfo.getValue()); } return new Pair<>(parent.get(s), weight.get(s)); } // union operation private void union(String u, String v, double value, Map parent, Map weight) { Pair rootU = find(u, parent, weight); Pair rootV = find(v, parent, weight); if (!rootU.getKey().equals(rootV.getKey())) { parent.put(rootU.getKey(), rootV.getKey()); // rootU / rootV = (u / rootU)^-1 * (u/v) * (v/rootV) // weight[rootU] = value * weight[v] / weight[u] weight.put(rootU.getKey(), (value * rootV.getValue()) / rootU.getValue()); } } } // A simple Pair class would be needed for Java < 8 or if not using javafx.util.Pair class Pair { private K key; private V value; public Pair(K key, V value) { this.key = key; this.value = value; } public K getKey() { return key; } public V getValue() { return value; } } ``` ### Algorithm 1. **Data Structures**: Use two maps: `parent` to store the parent of each variable in the disjoint set structure, and `weight` to store the value of `variable / parent[variable]`. 2. **Initialization**: Initially, each variable is its own parent (`parent[v] = v`) with a weight of 1.0 (`weight[v] = 1.0`). 3. **`find` Operation (with Path Compression)**: This is the key operation. `find(v)` returns the root of the set containing `v` and the value of `v / root`. * If `v` is its own parent, it's the root. Return `(v, 1.0)`. * Recursively call `find` on `v`'s parent to get the root of the set, `root`, and the value `parent[v] / root`. * **Path Compression**: Set `v`'s parent directly to `root`. * **Weight Update**: Update `weight[v]` to be `(v / old_parent) * (old_parent / root)`. This new `weight[v]` now represents `v / root`. 4. **`union` Operation**: To process an equation `A / B = V`: * Find the roots and weights for both A and B: `(rootA, weightA) = find(A)` and `(rootB, weightB) = find(B)`. * If the roots are different, merge the sets. For example, make `rootA` a child of `rootB`. * Set `parent[rootA] = rootB`. * Calculate the weight for this new link: `weight[rootA] = (V * weightB) / weightA`. This formula is derived from `A/B = V` by substituting `A = weightA * rootA` and `B = weightB * rootB`. 5. **Main Logic**: * **Build Phase**: Iterate through all equations, calling `union` for each one to build the disjoint sets. * **Query Phase**: For each query `C / D`: * If `C` or `D` are not in the data structure, the result is -1.0. * Call `find(C)` and `find(D)` to get their roots and weights relative to their roots. * If the roots are not the same, they are not connected; result is -1.0. * If the roots are the same, the result is `weightC / weightD`. # Solutions ### Java ```java class Solution { private Map p; private Map w; public double[] calcEquation(List> equations, double[] values, List> queries) { int n = equations.size(); p = new HashMap<>(); w = new HashMap<>(); for (List 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 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); } } ``` ### CPP ```cpp class Solution { public: unordered_map p; unordered_map w; vector calcEquation(vector> &equations, vector &values, vector> &queries) { int n = equations.size(); for (auto e : equations) { p[e[0]] = e[0]; p[e[1]] = e[1]; w[e[0]] = 1.0; w[e[1]] = 1.0; } for (int i = 0; i < n; ++i) { vector e = equations[i]; string a = e[0], b = e[1]; string pa = find(a), pb = find(b); if (pa == pb) continue; p[pa] = pb; w[pa] = w[b] * values[i] / w[a]; } int m = queries.size(); vector ans(m); for (int i = 0; i < m; ++i) { string c = queries[i][0], d = queries[i][1]; ans[i] = p.find(c) == p.end() || p.find(d) == p.end() || find(c) != find(d) ? -1.0 : w[c] / w[d]; } return ans; } string find(string x) { if (p[x] != x) { string origin = p[x]; p[x] = find(p[x]); w[x] *= w[origin]; } return p[x]; } }; ``` ### Python ```python class Solution: def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]: def find(x): if p[x] != x: origin = p[x] p[x] = find(p[x]) w[x] *= w[origin] return p[x] w = defaultdict(lambda: 1) p = defaultdict() for a, b in equations: p[a], p[b] = a, b for i, v in enumerate(values): a, b = equations[i] pa, pb = find(a), find(b) if pa == pb: continue p[pa] = pb w[pa] = w[b] * v / w[a] return [- 1 if c not in p or d not in p or find(c) != find(d) else w[c] / w[d] for c, d in queries] ```