Evaluate Division

Medium · Graphs · Explanation and code example

Floyd Warshall

How it works

Floyd-Warshall computes shortest paths between all pairs of nodes. Here, instead of distances, we compute the product of ratios. If we know a/b and b/c, then a/c = (a/b) * (b/c). We precompute all such transitive ratios.

This approach trades query time for preprocessing time. After running Floyd-Warshall, each query becomes a simple lookup.

Steps

  1. Build a graph where graph[a][b] = value for equation a/b = value, and graph[b][a] = 1/value.
  2. Run Floyd-Warshall: for each intermediate node k, and for each pair of nodes (i, j) connected through k, compute graph[i][j] = graph[i][k] * graph[k][j] if this path does not already exist.
  3. For each query (a, b):
    • If a is in the graph and b is reachable from a, return graph[a][b].
    • Otherwise, return -1.

Complexity

  • Time complexity: O(m + n ^ 3)
  • Space complexity: O(n ^ 2 + m)

Where n is the number of unique strings and m is the number of queries.

Things to watch for

Forgetting to Add Reciprocal Edges

When building the graph, each equation a / b = value must create two edges: a -> b with weight value AND b -> a with weight 1/value. Forgetting the reciprocal edge means you can only traverse the relationship in one direction, causing valid queries to return -1 when the path exists in reverse.

Not Handling Unknown Variables

A query might contain variables that never appeared in any equation. Before starting BFS/DFS, you must check if both the source and target variables exist in the graph. Attempting to traverse from a non-existent node will cause null pointer errors or infinite loops depending on your implementation.

Incorrect Weight Multiplication Order in Union-Find

In the weighted Union-Find approach, the weight calculation during union is subtle: when connecting rootX to rootY, the new weight for rootX must be value * weight[y] / weight[x]. Getting this formula wrong (such as dividing instead of multiplying, or using the wrong variables) will produce incorrect ratios for subsequent queries.

Python code example

import collections

class Solution:
    def calcEquation(self, equations, values, queries):
        graph = collections.defaultdict(dict)

        for (a, b), value in zip(equations, values):
            graph[a][b] = value
            graph[b][a] = 1.0 / value

        for k in graph:
            for i in graph[k]:
                for j in graph[k]:
                    if j not in graph[i]:
                        graph[i][j] = graph[i][k] * graph[k][j]

        result = []
        for a, b in queries:
            if a in graph and b in graph[a]:
                result.append(graph[a][b])
            else:
                result.append(-1.0)
        return result

C++ code example

class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        unordered_map<string, unordered_map<string, double>> graph;

        for (int i = 0; i < equations.size(); i++) {
            string a = equations[i][0];
            string b = equations[i][1];
            double value = values[i];
            graph[a][b] = value;
            graph[b][a] = 1.0 / value;
        }

        for (const auto& pair : graph) {
            const string& k = pair.first;
            for (const auto& pair1 : graph[k]) {
                const string& i = pair1.first;
                for (const auto& pair2 : graph[k]) {
                    const string& j = pair2.first;
                    if (!graph[i].count(j)) {
                        graph[i][j] = graph[i][k] * graph[k][j];
                    }
                }
            }
        }

        vector<double> result;
        for (const auto& query : queries) {
            const string& a = query[0];
            const string& b = query[1];
            if (!graph.count(a) || !graph[a].count(b)) {
                result.push_back(-1.0);
            } else {
                result.push_back(graph[a][b]);
            }
        }

        return result;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode Watch NeetCode on YouTube

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations