Evaluate Division: Graph Traversal with Weighted Edges

You are given a list of equations like a / b = 2.0 and b / c = 3.0, and then a list of queries like a / c = ?. Your job is to evaluate each query based on the equations you have, or return -1.0 if the answer cannot be determined.

This is LeetCode 399: Evaluate Division, and it is one of the cleanest examples of how graph modeling turns an abstract math problem into a reachability problem. Once you see the graph, the solution writes itself.

The problem

Given equations (pairs of variables) and values (the result of dividing the first variable by the second), answer a list of queries. Each query asks for the result of dividing one variable by another.

Example:

• equations = [["a","b"],["b","c"]], values = [2.0, 3.0]
• queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
• Output: [6.0, 0.5, -1.0, 1.0, -1.0]

The equation a / b = 2.0 means "a is 2 times b." From a / b = 2.0 and b / c = 3.0, you can derive a / c = 6.0 by chaining the two divisions together.

Why graph traversal works

The core insight is that each equation defines a relationship between two variables, and that relationship has a numeric weight. That is exactly what a weighted directed graph models.

For each equation a / b = k:

• Add an edge from a to b with weight k
• Add an edge from b to a with weight 1/k

Now, to evaluate a query like a / c, you find a path from a to c in the graph and multiply all the edge weights along the way. If no path exists, the answer is -1.0.

Why does multiplying edge weights work? Because a / c = (a / b) * (b / c). Each edge represents one division. Walking from a to b gives you a / b. Walking from b to c gives you b / c. Multiplying them cancels out the intermediate variable b, leaving you with a / c. This is just how fractions chain together.

Step-by-step walkthrough

Let's trace through the query a / c = ? using BFS. We have equations a / b = 2.0 and b / c = 3.0.

The BFS carries a running product along each path. When it reaches the target node, that product is the answer. If the queue empties without finding the target, the query returns -1.0.

The code

from collections import defaultdict, deque

def calcEquation(equations, values, queries):
    graph = defaultdict(dict)

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

    def bfs(src, dst):
        if src not in graph or dst not in graph:
            return -1.0
        if src == dst:
            return 1.0

        visited = {src}
        queue = deque([(src, 1.0)])

        while queue:
            node, product = queue.popleft()
            for neighbor, weight in graph[node].items():
                if neighbor == dst:
                    return product * weight
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append((neighbor, product * weight))

        return -1.0

    return [bfs(a, b) for a, b in queries]

The graph is built using a defaultdict(dict), where graph[a][b] = k means there is an edge from a to b with weight k. For each equation, we add both the forward and reciprocal edges.

The BFS function starts at src with a product of 1.0. At each step, it multiplies the current product by the edge weight and checks if it has reached dst. The visited set prevents infinite loops in cyclic graphs. If the target is never found, it returns -1.0.

Two quick checks handle special cases up front: if either variable is not in the graph, the answer is -1.0. If src == dst (and the variable exists), the answer is 1.0 because any number divided by itself is 1.

Complexity analysis

E is the number of equations (edges), V is the number of unique variables (vertices), and Q is the number of queries.

Time: Building the graph takes O(E). Each BFS query visits at most V nodes and E edges, so all queries together cost O(Q * (V + E)). Since E is typically small relative to V^2, this simplifies to O(E + Q * V) in practice.

Space: The adjacency list stores 2E entries (one forward, one reciprocal per equation). The BFS visited set uses O(V) per query. Total: O(E).

The building blocks

Weighted graph modeling

The hardest part of this problem is not the BFS. It is recognizing that division relationships form a weighted graph. Once you build the adjacency list, the rest is standard graph traversal with a small twist (carrying a running product instead of just tracking distance).

This same "model as a graph" pattern shows up in many problems:

• Currency exchange: converting between currencies is multiplying exchange rates along a path
• Unit conversion: meters to inches through intermediate units
• Transitive relationships: any relationship that chains through intermediate nodes

Edge cases

• Variable not in any equation: return -1.0. Even x / x is -1.0 if x was never mentioned in the equations.
• Self-division (a / a): return 1.0, but only if a appears in the graph.
• Single equation chain: a / b = 2.0 alone. Queries a / b, b / a, a / a, and b / b all have answers. Anything involving other variables does not.
• Disconnected components: if a and c are in separate graph components with no path between them, return -1.0.
• Long chains: a / b = 2, b / c = 3, c / d = 4. Query a / d requires traversing the full chain and multiplying 2 * 3 * 4 = 24.

From understanding to recall

You have seen how division equations map to a weighted directed graph and how BFS finds answers by multiplying edge weights along paths. The logic is clean. But in an interview, you need to write the graph construction, the BFS with a running product, and the edge-case checks from memory.

The details trip people up. Remembering to add reciprocal edges. Checking whether a variable exists before running BFS. Carrying the product through the queue instead of tracking distance. These are the things that slip away between reading a solution and writing one under pressure.

Spaced repetition locks in those details. You practice building the weighted adjacency list and writing the BFS with a product accumulator at increasing intervals. After a few rounds, the pattern is automatic. You do not rederive it. You just write it.

Related posts

• Course Schedule - graph traversal with adjacency lists and cycle detection
• Clone Graph - BFS graph traversal with node reconstruction
• Pacific Atlantic Water Flow - multi-source graph traversal on a grid

CodeBricks breaks Evaluate Division into its graph-modeling and BFS-with-accumulator building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a weighted graph problem appears in your interview, you do not hesitate. You just write it.