Evaluate Division

Practice Link

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 — evaluating the queries will not result in division by zero, and there is no contradiction. Variables that do not occur in the list of equations are undefined, so the answer cannot be determined for them.

Intuition#

Each equation A / B = v is really a relationship between two nodes in a graph, not just a fact about numbers. Model every variable as a node, and every equation as two directed, weighted edges: A → B with weight v (since A = v × B), and B → A with weight 1/v (the inverse relationship).

Once that graph exists, C / D is just the product of edge weights along any path from C to D — the intermediate variables cancel out telescopically: (C/x1) × (x1/x2) × ... × (xk/D) = C/D. So the problem reduces to: build the graph from the equations, then for each query, DFS from C toward D, multiplying the running product by each edge weight as you traverse, and return that product the moment you land on D.

Two things can make a query unanswerable:

• Either variable is undefined — never appeared in any equation, so it isn't a node in the graph at all.
• No path connects them — both variables are defined, but live in different connected components (e.g., a fact about a and b, and a separate, unrelated fact about x and y — asking for a/x is meaningless).

The visited set exists purely to prevent infinite loops on cycles (e.g., a → b → a), and doesn't need to be un-marked on backtrack — the "no contradiction" guarantee means every path between two connected variables yields the same product, so there's never a reason to re-explore a node from a different path.

Solution#

class Solution {
public:

    double dfs(
        string curr, 
        string dest, 
        unordered_map<string, vector<pair<string, double>>> &adjList,
        unordered_set<string> &visited,
        double eval
    ){
        if(adjList.find(curr) == adjList.end() || adjList.find(dest) == adjList.end())
            return -1;
        if(curr == dest)
            return eval;

        visited.insert(curr);

        for(auto [next, div]: adjList[curr]){
            if(visited.find(next) == visited.end()){
                double res = dfs(next, dest, adjList, visited, eval * div);
                if(res != -1)
                    return res;
            }
            
        }
        return -1;
    }

    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        unordered_map<string, vector<pair<string, double>>> adjList;

        for(int i=0;i<equations.size();i++){
            string source = equations[i][0];
            string dest = equations[i][1];

            adjList[source].push_back({dest, values[i]});
            adjList[dest].push_back({source, 1/values[i]});
        }

        int q = queries.size();
        vector<double> ans(q);
        for(int i = 0; i < q; i++){
            string s = queries[i][0];
            string d = queries[i][1];

            unordered_set<string> visited;
            double eval = 1;
            ans[i] = dfs(s, d, adjList, visited, eval);
        }
        return ans;
    }
};

eval is the running product carried down the recursion — it starts at 1 for each fresh query and gets multiplied by each edge's weight as the DFS descends, so by the time curr == dest is hit, eval already holds the full C/D ratio.

Worth noting: the adjList.find(...) undefined-variable check re-runs on every recursive call, even though only the very first call actually needs it (dest's membership never changes across the recursion, and curr is always a valid node by construction — you only ever recurse into neighbors that are already keys in adjList). It's harmless, just a small amount of repeated work.

Dry run#

equations = [["a","b"],["b","c"]], values = [2.0, 3.0] → graph edges: a→b (2.0), b→a (0.5), b→c (3.0), c→b (1/3).

Query a / c:

• dfs(a, c, eval=1) → a ≠ c, mark a visited, try neighbor (b, 2.0)
• dfs(b, c, eval=2) → b ≠ c, mark b visited, skip visited a, try neighbor (c, 3.0)
• dfs(c, c, eval=6) → c == c, return 6

Result: a/c = 6.0 ✓ (checks out: a = 2b, b = 3c, so a = 6c).

Query b / a:

• dfs(b, a, eval=1) → b ≠ a, mark b visited, try neighbor (a, 0.5)
• dfs(a, a, eval=0.5) → a == a, return 0.5

Result: b/a = 0.5 ✓.

Query a / e (e never appears in any equation): dfs(a, e, ...) immediately fails the adjList.find(dest) == end() check → returns -1.0.

Complexities#

Let E = number of equations, V = number of distinct variables, Q = number of queries.

Time Complexity: O(E) to build the graph, plus O(Q × (V + E)) for the queries — each query's DFS can, in the worst case, traverse every node and edge before determining the two variables are unconnected.

Space Complexity: O(V + E) for the adjacency list, plus O(V) per query for the visited set and recursion stack depth.