Log inSign up
mediumLeetCodeNot Started

Evaluate Division

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Graph
Solve on LeetCode
Lesson

Problem Statement

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].

You are also given some queries, where queries[j] = [Cj, Dj] represents the j^{th} 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.

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 lowercase English letters and digits.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Model ratio and conversion equations as weighted directed graphs.
  • Apply path finding with multiplicative chain rule accumulation.
  • Implement bidirectional edge insertion with reciprocal weights (v and 1/v).
  • Understand Weighted Disjoint Set Union (DSU with multipliers) for constant-time query answering.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Whenever equations specify ratios or conversion rates between variable pairs (A/B = v) and ask to evaluate unknown ratios (C/D), model each variable as a graph vertex and ratios as multiplicative directed edge weights.

1. Floyd-Warshall All-Pairs Transitive Division

Intuition

Extract all unique variables. Initialize a 2D table ratio[u][v] with -1.0. For each equation, set ratio[A][B] = val, ratio[B][A] = 1/val, and ratio[A][A] = 1.0. Then run Floyd-Warshall with multiplication: if ratio[i][k] > 0 && ratio[k][j] > 0, then ratio[i][j] = ratio[i][k] * ratio[k][j]. All queries are then answered in O(1) time.

Algorithm

  1. Map each unique variable string to an integer index 0 \dots V - 1.
  2. Initialize ratio matrix of size V × V with -1.0.
  3. For each vertex i, set ratio[i][i] = 1.0.
  4. For each equation (A, B) with value v:
  5. ratio[u][v] = val, ratio[v][u] = 1.0 / val.
  6. Run Floyd-Warshall: triple loop over k, i, j:
  7. If ratio[i][k] > 0 && ratio[k][j] > 0:
  8. ratio[i][j] = ratio[i][k] * ratio[k][j].
  9. For each query (C, D):
  10. If C or D not in map, answer is -1.0.
  11. Else answer is ratio[idC][idD].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_map>
5
6std::vector<double> calcEquationFloyd(std::vector<std::vector<std::string>>& equations,
7 std::vector<double>& values,
8 std::vector<std::vector<std::string>>& queries) {
9 std::unordered_map<std::string, int> idMap;
10 int id = 0;
11 for (const auto& eq : equations) {
12 if (!idMap.count(eq[0])) idMap[eq[0]] = id++;
13 if (!idMap.count(eq[1])) idMap[eq[1]] = id++;
14 }
15
16 int V = id;
17 std::vector<std::vector<double>> ratio(V, std::vector<double>(V, -1.0));
18 for (int i = 0; i < V; ++i) ratio[i][i] = 1.0;
19
20 for (size_t i = 0; i < equations.size(); ++i) {
21 int u = idMap[equations[i][0]], v = idMap[equations[i][1]];
22 ratio[u][v] = values[i];
23 ratio[v][u] = 1.0 / values[i];
24 }
25
26 for (int k = 0; k < V; ++k) {
27 for (int i = 0; i < V; ++i) {
28 for (int j = 0; j < V; ++j) {
29 if (ratio[i][k] > 0 && ratio[k][j] > 0) {
30 ratio[i][j] = ratio[i][k] * ratio[k][j];
31 }
32 }
33 }
34 }
35
36 std::vector<double> results;
37 for (const auto& q : queries) {
38 if (!idMap.count(q[0]) || !idMap.count(q[1])) {
39 results.push_back(-1.0);
40 } else {
41 results.push_back(ratio[idMap[q[0]]][idMap[q[1]]]);
42 }
43 }
44 return results;
45}
46
47int main() {
48 std::vector<std::vector<std::string>> eq = {{"a","b"},{"b","c"}};
49 std::vector<double> vals = {2.0, 3.0};
50 std::vector<std::vector<std::string>> q = {{"a","c"},{"b","a"},{"a","e"}};
51 auto res = calcEquationFloyd(eq, vals, q);
52 std::cout << "Evaluate Division (Floyd): ";
53 for (double d : res) std::cout << d << " ";
54 std::cout << std::endl;
55 return 0;
56}

Time & Space Complexity

  • Time complexity: O(V^3 + Q) where V is the number of unique variables (at most 40) and Q is queries count.
  • Space complexity: O(V^2) for the all-pairs ratio table.

2. Breadth-First Search (BFS) per Query

Intuition

Build an adjacency list where each node has directed edges to its neighbors with weight v. For each query (C, D), perform a BFS starting at C with product accumulator 1.0. If D is reached, return the product. If queue empties without reaching D, return -1.0.

Algorithm

  1. Construct adjacency list adj: adj[A].push({B, val}), adj[B].push({A, 1.0/val}).
  2. For each query [C, D]:
  3. If C or D not in adj, return -1.0.
  4. If C == D, return 1.0.
  5. Initialize BFS queue with (C, 1.0) and visited set.
  6. While queue not empty:
  7. Pop (curr, prod).
  8. If curr == D, answer found -> save prod.
  9. Explore unvisited neighbors of curr with updated prod * weight.
  10. If not found, return -1.0.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_map>
5#include <unordered_set>
6#include <queue>
7
8double bfsQuery(const std::string& start, const std::string& end,
9 std::unordered_map<std::string, std::vector<std::pair<std::string, double>>>& adj) {
10 if (!adj.count(start) || !adj.count(end)) return -1.0;
11 if (start == end) return 1.0;
12
13 std::queue<std::pair<std::string, double>> q;
14 std::unordered_set<std::string> visited;
15
16 q.push({start, 1.0});
17 visited.insert(start);
18
19 while (!q.empty()) {
20 auto [curr, prod] = q.front();
21 q.pop();
22
23 if (curr == end) return prod;
24
25 for (const auto& [next, weight] : adj[curr]) {
26 if (!visited.count(next)) {
27 visited.insert(next);
28 q.push({next, prod * weight});
29 }
30 }
31 }
32 return -1.0;
33}
34
35std::vector<double> calcEquationBFS(std::vector<std::vector<std::string>>& equations,
36 std::vector<double>& values,
37 std::vector<std::vector<std::string>>& queries) {
38 std::unordered_map<std::string, std::vector<std::pair<std::string, double>>> adj;
39 for (size_t i = 0; i < equations.size(); ++i) {
40 adj[equations[i][0]].push_back({equations[i][1], values[i]});
41 adj[equations[i][1]].push_back({equations[i][0], 1.0 / values[i]});
42 }
43
44 std::vector<double> results;
45 for (const auto& q : queries) {
46 results.push_back(bfsQuery(q[0], q[1], adj));
47 }
48 return results;
49}
50
51int main() {
52 std::vector<std::vector<std::string>> eq = {{"a","b"},{"b","c"}};
53 std::vector<double> vals = {2.0, 3.0};
54 std::vector<std::vector<std::string>> q = {{"a","c"},{"b","a"},{"a","e"}};
55 auto res = calcEquationBFS(eq, vals, q);
56 std::cout << "Evaluate Division (BFS): ";
57 for (double d : res) std::cout << d << " ";
58 std::cout << std::endl;
59 return 0;
60}

Time & Space Complexity

  • Time complexity: O(Q * (V + E)) where Q is number of queries, V is unique variables, and E is equations count.
  • Space complexity: O(V + E) for adjacency list and BFS queue.

3. Weighted Disjoint Set Union (Union-Find with Weights)

Intuition

In DSU, each node u points to a parent. In Weighted DSU, we also store weight[u] = u / parent[u]. With path compression, when u is updated to point directly to root R, its weight becomes weight[u] = weight[u] * weight[old_parent]. To answer query C / D: if find(C) != find(D), they are in different components (return -1.0). If they share root R, then C / D = (C / R) / (D / R) = \text{weight}[C] / \text{weight}[D] in O(\alpha(N)) time!

Algorithm

  1. Initialize parent map: parent[x] = x, weight[x] = 1.0.
  2. Define find(x) with path compression:
  3. If parent[x] != x:
  4. origin = parent[x]
  5. parent[x] = find(origin)
  6. weight[x] *= weight[origin]
  7. Return parent[x].
  8. Define union(x, y, value) (x / y = value):
  9. rootX = find(x), rootY = find(y)
  10. If rootX != rootY:
  11. parent[rootX] = rootY
  12. weight[rootX] = value * weight[y] / weight[x]
  13. Process each equation with union.
  14. For each query [C, D]:
  15. If C or D not in parent, return -1.0.
  16. rootC = find(C), rootD = find(D)
  17. If rootC != rootD, return -1.0.
  18. Else return weight[C] / weight[D].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_map>
5
6class WeightedDSU {
7 std::unordered_map<std::string, std::string> parent;
8 std::unordered_map<std::string, double> weight;
9public:
10 void add(const std::string& x) {
11 if (!parent.count(x)) {
12 parent[x] = x;
13 weight[x] = 1.0;
14 }
15 }
16
17 std::string find(const std::string& x) {
18 if (parent[x] != x) {
19 std::string origin = parent[x];
20 parent[x] = find(origin);
21 weight[x] *= weight[origin];
22 }
23 return parent[x];
24 }
25
26 void unite(const std::string& x, const std::string& y, double val) {
27 add(x); add(y);
28 std::string rootX = find(x);
29 std::string rootY = find(y);
30 if (rootX != rootY) {
31 parent[rootX] = rootY;
32 weight[rootX] = val * weight[y] / weight[x];
33 }
34 }
35
36 double query(const std::string& x, const std::string& y) {
37 if (!parent.count(x) || !parent.count(y)) return -1.0;
38 std::string rootX = find(x);
39 std::string rootY = find(y);
40 if (rootX != rootY) return -1.0;
41 return weight[x] / weight[y];
42 }
43};
44
45std::vector<double> calcEquation(std::vector<std::vector<std::string>>& equations,
46 std::vector<double>& values,
47 std::vector<std::vector<std::string>>& queries) {
48 WeightedDSU dsu;
49 for (size_t i = 0; i < equations.size(); ++i) {
50 dsu.unite(equations[i][0], equations[i][1], values[i]);
51 }
52
53 std::vector<double> results;
54 for (const auto& q : queries) {
55 results.push_back(dsu.query(q[0], q[1]));
56 }
57 return results;
58}
59
60int main() {
61 std::vector<std::vector<std::string>> eq = {{"a","b"},{"b","c"}};
62 std::vector<double> vals = {2.0, 3.0};
63 std::vector<std::vector<std::string>> q = {{"a","c"},{"b","a"},{"a","e"}};
64 auto res = calcEquation(eq, vals, q);
65 std::cout << "Optimal Evaluate Division (DSU): ";
66 for (double d : res) std::cout << d << " ";
67 std::cout << std::endl;
68 return 0;
69}

Time & Space Complexity

  • Time complexity: O((N + Q) * alpha(V)) practically O(N + Q) linear time, answering each query in near constant amortized time.
  • Space complexity: O(V) for the parent and weight maps.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Floyd-WarshallO(V^3 + Q)O(V^2)All pairs precomputed; queries answered in O(1).Cubic preprocessing time; impractical if V exceeds a few hundred.
2.BFS per QueryO(Q * (V + E))O(V + E)Simple to write; intuitive path exploration on adjacency list.Performs full graph traversal for every query.
3.Weighted Disjoint Set UnionOptimalO((N + Q) * alpha(V))O(V)Asymptotically optimal; online union and queries in near O(1) amortized time.Requires implementing path compression with multiplication.

Common Pitfalls & Crucial Edge Cases

Returning 1.0 for [x, x] even when x does not exist in equations.

The problem specifies that if a variable is unknown, the answer cannot be determined and must return -1.0.

Adding weights instead of multiplying in Weighted DSU.

Division ratios multiply: (A/B) * (B/C) = A/C.

Crucial Edge Cases to Validate:

  • Query asking for x / x where x is a known variable — Returns 1.0.
  • Query asking for x / x where x has never appeared in equations — Returns -1.0 (unknown variable).
  • Two variables belong to disjoint components — No connecting path exists; returns -1.0.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the graph conversion: 'Variables are vertices, ratios are directed edge weights with reciprocals, and queries evaluate path products.'
  2. Explain the Weighted DSU approach: show how x / parent ratios multiply along path compression to answer queries in near O(1) time.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does the directed edge from B to A have weight 1.0 / val when A / B = val?

2.What should be returned if variable C has never appeared in any equation?

3.How does Weighted DSU handle path compression for weight values?

Back to DSA Sheet