Evaluate Division

Table of Contents +

You know that a / b = 2 and b / c = 3. So what is a / c? Your brain multiplies along the chain to get 6. This question asks you to teach a computer that same chain trick. The fix is to turn the ratios into a graph and walk the path.

🎯 The Problem

You answer division questions from a set of known ratios. Here are the rules.

  • You get a list of equations like a / b = 2.0.
  • You get a list of questions like “what is a / c?”.
  • For each question, return the answer if you can work it out from the known equations.
  • If you cannot reach it, return -1.0.
  • If a value appears in a question but never in any equation, return -1.0 too.
Input:
  equations = [["a", "b"], ["b", "c"]]
  values    = [2.0, 3.0]
  queries   = [["a", "c"], ["b", "a"], ["x", "x"]]


Output: [6.0, 0.5, -1.0]


Explanation:
  a / c = (a / b) * (b / c) = 2.0 * 3.0 = 6.0
  b / a = 1 / (a / b)       = 1 / 2.0   = 0.5
  x is unknown, so the answer is -1.0

Think of each variable as a place on a map. Each equation is a road between two places with a number on it. The number is the ratio, which is how much bigger one place is than the other. To answer a question you walk the road and multiply the numbers along the way.

Here is the graph for the example. Each arrow carries the ratio in that direction.

2.0

0.5

3.0

0.333

a

b

c

🐢 Approach 1: Weighted Graph DFS (Better)

The idea in one line: turn the ratios into a graph, then walk from one variable to the other and multiply the edge weights.

The idea:

  • Each variable is a node.
  • For a / b = 2.0, add edge a to b with weight 2.0 and edge b to a with weight 0.5.
  • The reverse edge is just one over the forward one.

How it works:

  • To answer “what is a / c?”, start at a and run depth-first search to c.
  • Depth-first search follows one path as deep as it goes before backing up.
  • Multiply the weights as you step along each edge.
  • When you reach c, the product is the answer.
  • Carry a “visited” set so the search never loops forever.
  • If a variable is missing, or no path reaches the target, return -1.0.

Why it is weak:

  • Each query may walk the whole graph again.
  • For Q queries this is Q separate searches.
  • Cost per query is O(V + E), so many queries get slow.

Here is the weighted-DFS code:

evaluate_division_dfs.py
def calc_equation(equations, values, queries):
    graph = {}
    for (a, b), v in zip(equations, values):
        graph.setdefault(a, []).append((b, v))
        graph.setdefault(b, []).append((a, 1 / v))
    def dfs(src, dst, seen):
        if src == dst: return 1
        seen.add(src)
        for nei, weight in graph.get(src, []):
            if nei not in seen:
                ans = dfs(nei, dst, seen)
                if ans != -1: return weight * ans
        return -1
    return [dfs(a, b, set()) if a in graph and b in graph else -1 for a, b in queries]

⚡ Approach 2: Union-Find With Ratios (Best)

The idea in one line: group connected variables once, store each variable’s ratio to its group root, then answer any query almost instantly.

The idea:

  • Union-find points each variable to a parent and stores its ratio to that parent.
  • The root of a group is a shared reference point.
  • So every variable in a group knows its value relative to the same root.

How it works:

  • To union a and b with a / b = 2.0, attach one root under the other.
  • Adjust the stored ratio so the math stays correct.
  • To answer a query, find the root of both variables.
  • If they share a root, the answer is ratio[a] / ratio[b].
  • If the roots differ, there is no path, so return -1.0.

Why it is fast:

  • The groups are built once, up front.
  • After that, each query is almost constant time.

The DFS version reads cleanly in all five languages, so the code below uses DFS. Here is how a single query walks the graph and multiplies.

Query a / c

At a, product = 1.0

Step a to b, multiply 2.0, product = 2.0

Step b to c, multiply 3.0, product = 6.0

Reached c, return 6.0

Steps to Solve

  1. Build a graph. For each equation u / v = w, add edge u to v with weight w and edge v to u with weight 1 / w.
  2. For each query (src, dst), if either name is missing from the graph, record -1.0.
  3. Otherwise run depth-first search from src, carrying the running product of weights.
  4. Mark nodes visited so you never loop.
  5. When you reach dst, the running product is the answer.
  6. If the search ends without reaching dst, record -1.0.

This Python version stores the graph as a dictionary of neighbor lists and uses a recursive DFS that multiplies weights.

evaluate_division.py
def evaluate_division(equations, values, queries):
    graph = {}                              # node -> list of (neighbor, ratio)
    for (u, v), w in zip(equations, values):
        graph.setdefault(u, []).append((v, w))
        graph.setdefault(v, []).append((u, 1.0 / w))  # reverse edge


    def dfs(node, target, product, visited):
        if node == target:
            return product                  # reached the goal
        visited.add(node)
        for nxt, ratio in graph[node]:
            if nxt not in visited:
                res = dfs(nxt, target, product * ratio, visited)
                if res >= 0:
                    return res              # path found, pass it up
        return -1.0                         # dead end


    answers = []
    for src, dst in queries:
        if src not in graph or dst not in graph:
            answers.append(-1.0)            # unknown variable
        else:
            answers.append(dfs(src, dst, 1.0, set()))
    return answers




equations = [["a", "b"], ["b", "c"]]
values = [2.0, 3.0]
queries = [["a", "c"], ["b", "a"], ["x", "x"]]
print(evaluate_division(equations, values, queries))

The output of the above code will be:

[6.0, 0.5, -1.0]

Let us read the Python version line by line, because the graph build and the DFS are the heart of it.

The first loop builds the graph. For each equation u / v = w we add (v, w) to u’s list. That is the forward road. We also add (u, 1.0 / w) to v’s list. That is the reverse road, because if a / b = 2 then b / a = 0.5. setdefault(u, []) creates an empty list the first time we see a node.

dfs(node, target, product, visited) is the search. The product is the running multiply of every weight we crossed so far. If node == target, that product is the answer, so we return it.

We add the node to visited before exploring, so the search never circles back and loops forever.

The loop tries each neighbor. We call dfs with product * ratio, stepping across that edge. If the deeper call returns a value that is not -1, we found the target down that branch, so we pass it straight up.

If every branch dead-ends, we return -1.0. Since real division answers are always positive here, the res >= 0 check cleanly separates “found” from “not found”.

The query loop guards the unknown case first. If src or dst was never in any equation, we cannot know the answer, so we append -1.0 without searching. Otherwise we start a fresh DFS with product = 1.0 and an empty visited set.

⏱️ Time and Space Complexity

Building the graph is O(E), where E is the number of equations. Each query runs a DFS that may touch every node and edge, so one query is O(V + E). With Q queries the DFS approach is O(Q × (V + E)). The union-find approach builds groups once and then answers each query almost instantly. Both store the graph or the parent links in O(V + E) space.

Approach Time Complexity Space Complexity
Weighted graph DFS (better) O(Q × (V + E)) O(V + E)
Union-find with ratios (best) O((E + Q) × α) O(V)

Tip

The reverse edge is the part people forget. Every equation gives you two roads, the forward ratio and one over it. Without the reverse edge, half the queries fail.

🧩 Key Takeaways

  • ✅ Turn each equation into two graph edges, the ratio and one over it.
  • ✅ A division query is just a path. Multiply the edge weights as you walk.
  • ✅ Use DFS with a visited set so the search never loops forever.
  • ✅ If a variable never appears in any equation, the answer is -1.0.
  • ✅ Union-find with stored ratios answers each query almost instantly after setup.

Check Your Knowledge

 4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    How do you answer a query like a / c using the graph?

    Why: A division chain multiplies, so you multiply the ratios along the path from a to c.

  2. 2

    For the equation a / b = 2.0, what reverse edge do you add?

    Why: Since a / b = 2.0, the reverse b / a = 1 / 2.0 = 0.5.

  3. 3

    What should a query return if one of its variables never appears in any equation?

    Why: An unknown variable means the answer cannot be derived, so you return -1.0.

  4. 4

    What is the time cost of answering Q queries with the DFS approach?

    Why: Each query may run a full DFS over the graph, so Q queries cost O(Q × (V + E)).

Score: 0 / 4

🚀 What’s Next?

Previous Making a Large Island Next All Ancestors of a Node in a Directed Acyclic Graph