LeetCode 399: Evaluate Division — Python Solution

LeetCode 399: Evaluate Division is a Medium graph general problem. This Python walkthrough develops a weighted graph search solution, ties every code decision to a concrete invariant, and includes the regression check used before publication.

This independent guide paraphrases the task rather than reproducing LeetCode’s prompt. Use the official page for the exact statement, examples, constraints, and submission runner.

Recognizing the pattern

Graph traversal separates reachability from representation: adjacency describes possible moves, while a visited structure prevents repeated work.

For this problem specifically, represent each equation as two reciprocal weighted edges. For a query, search for a path and multiply weights along it. The invariant worth writing beside the code is: The accumulated product equals the ratio from the query source to the current graph node.

Step-by-step algorithm

1. Identify the input state consumed by calcEquation(equations, values, queries) and initialize the data required by the weighted graph search pattern.
2. Represent each equation as two reciprocal weighted edges. For a query, search for a path and multiply weights along it.
3. After each update, verify the page’s central invariant: The accumulated product equals the ratio from the query source to the current graph node.
4. Finish only after the boundary behavior is covered: Unknown variables and disconnected pairs return -1; a known variable divided by itself is one.

Python solution

from collections import defaultdict

class Solution:
    def calcEquation(self, equations, values, queries):
        graph = defaultdict(list)
        for (a, b), value in zip(equations, values):
            graph[a].append((b, value)); graph[b].append((a, 1.0 / value))
        def search(start, end):
            if start not in graph or end not in graph: return -1.0
            stack, seen = [(start, 1.0)], {start}
            while stack:
                node, product = stack.pop()
                if node == end: return product
                for neighbor, weight in graph[node]:
                    if neighbor not in seen:
                        seen.add(neighbor); stack.append((neighbor, product * weight))
            return -1.0
        return [search(a, b) for a, b in queries]

Reading the implementation

The main entry point is calcEquation(equations, values, queries). The named working state includes graph, stack, node; those variables make the weighted graph search state visible instead of hiding it in incidental control flow.

The implementation uses 3 loops with separate responsibilities, so preprocessing and the main traversal can each stay linear in their own input. Early returns stop as soon as the answer is forced, avoiding work that cannot change the result. In concrete terms, represent each equation as two reciprocal weighted edges. For a query, search for a path and multiply weights along it.

Correctness argument

Initialization. The data structure starts with exactly the information known before any input element is processed.

Preservation. Represent each equation as two reciprocal weighted edges. For a query, search for a path and multiply weights along it. Each update records the current item without invalidating earlier decisions; consequently, the accumulated product equals the ratio from the query source to the current graph node.

Termination. The traversal consumes a finite input or finite state space. At the end, the invariant covers the complete input, which is precisely the condition required for the returned result.

Complexity and trade-offs

O((V+E) per query) time and O(V+E) space. The auxiliary-space figure excludes the returned output unless the output itself is the structure being built.

DFS and BFS often have the same asymptotic cost; choose DFS for recursive structure and BFS when distance or processing order matters. That comparison is useful in an interview because it explains why the final implementation is preferable, not merely that it passes.

Regression check

The published implementation belongs to a 100-problem suite that is compiled and exercised behaviorally before deployment.

One reference assertion from that suite is shown below. It targets the normal path while the edge conditions in the next section cover the failure-prone boundaries.

values=Solution().calcEquation([["a","b"],["b","c"]],[2.0,3.0],[["a","c"],["b","a"],["a","e"]]); assert values==[6.0,0.5,-1.0]

Common mistakes and edge cases

• Problem-specific boundary: Unknown variables and disconnected pairs return -1; a known variable divided by itself is one.
• Pattern-level pitfall: Mark a state when it is discovered rather than after all of its neighbors are processed, or cycles can enqueue it repeatedly.
• Invariant check: after every update, confirm that the accumulated product equals the ratio from the query source to the current graph node.

Interview review checklist

• Explain why weighted graph search matches the structure of this input.
• State the invariant in one sentence before tracing code: The accumulated product equals the ratio from the query source to the current graph node.
• Derive O((V+E) per query) time and O(V+E) space from how many times each element or state is visited.
• Test the boundary explicitly: Unknown variables and disconnected pairs return -1; a known variable divided by itself is one.

Browse the searchable 100 LeetCode Python Solutions hub. Previous: 133. Clone Graph · Next: 207. Course Schedule