399. Evaluate Division

399

MediumGraph DFS and BFSDFS on a graphWeighted graph path product

Evaluate Division

You are given equations of the form a / b = value, meaning variable a divided by variable b equals value. For each query x / y, return the computed value if it can be derived by chaining known equations, otherwise return -1.0. Queries involving a variable never seen in any equation also return -1.0.

Open official problem prompt ↗

In plain English

Answer division queries between variables using only the ratios given by a handful of known equations.

Picture it like this

Currency exchange: if 1 dollar = 2 euros and 1 euro = 3 pesos, then dollars-to-pesos is 2*3 = 6. Chain the conversion rates along a path, and going backward uses the reciprocal rate.

Example

Input: 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]
Why: a/c = (a/b)*(b/c) = 2*3 = 6; b/a = 1/2 = 0.5; e is unknown so -1; a/a = 1; x never appears so -1.

Constraints

1 <= equations.length <= 20equations[i].length == 21 <= queries.length <= 20values[i] > 0.0 and 0.0 < values[i] <= 20.0Variables are strings of 1-5 lowercase letters

Pattern lesson

See the pattern, then code

Weighted graph path product

↗

Graph DFS and BFS

Connected components, grids, reachability, or unweighted shortest paths.. Model each variable as a node. An equation a/b = k gives a directed edge a->b with weight k and b->a with weight 1/k. The value of x/y is the product of edge weights along any path from x to y.

New words, made simpleKnow these before the algorithm

Directed weighted edge: a->b with weight k encodes a/b = k; the reverse edge carries 1/k.
Path product: Multiplying the weights along a route from x to y yields x/y.
Visited set: Tracks nodes on the current DFS path to prevent infinite loops in cyclic graphs.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Best choiceDFS per query

Simple and easily fast enough for the tiny constraints here.

Build the bidirectional ratio graph once, then depth-first search each query multiplying weights.

Time O(q*(V+E))Space O(V+E)

Floyd-Warshall closure

Great when there are many queries, but overkill for at most 20 variables and queries.

Precompute the ratio between every pair of variables with an all-pairs product relaxation, then answer each query in O(1).

Time O(V^3)Space O(V^2)

The rule we keep true

Invariant

During a DFS the accumulated product from the start node to the current node equals start/current, so on reaching the target the product equals start/target.

Why this is correct

Reasoning

Division ratios compose multiplicatively, so any path from x to y multiplies to x/y regardless of the route (the graph is consistent). Adding reverse edges with reciprocal weights lets the search move in either direction, and the visited set guarantees termination.

The algorithm in three movesSay these aloud before coding

1Build an adjacency map with both directions and reciprocal weights

graph: a->b=2, b->a=0.5, b->c=3, c->b=1/3

2For each query, DFS from source to target multiplying weights

query a/c: a->b (2) then b->c (3)

3Return 1.0 immediately if source equals target and is known

product 2*3 = 6.0

4Return -1.0 if either variable is unknown or no path exists

5Use a visited set to avoid cycling

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Reada/b=2, b/c=3

2 · AskRecord edges both ways

3 · Update statea->b=2, b->a=0.5, b->c=3, c->b=0.333

4 · ResultGraph ready

Key takeaway

Path a -> b -> c multiplies edge weights 2 and 3 to answer a/c = 6.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-7Graph build
Each equation adds a forward edge with the ratio and a backward edge with its reciprocal.
2
Lines 9-11Base cases
Unknown variable returns -1.0; reaching the destination returns the identity 1.0.
3
Lines 12-18Explore neighbors
Multiply the current edge weight by the recursive result once a valid path is found.
4
Lines 20Answer queries
Run a fresh DFS with a new visited set for each query.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

A query where source equals target but the variable is known -> 1.0
A variable that appears in no equation -> -1.0
Two variables in separate disconnected components -> -1.0
A query that is exactly a stored equation (single edge)

Common beginner mistakes

Returning 1.0 for a/a when a was never defined — the spec requires -1.0 for unknown variables
Forgetting the reciprocal reverse edge, so backward queries fail
Sharing one visited set across queries instead of resetting it
Comparing floats with a strict !=; here -1.0 is a clean sentinel so it is safe, but never derive it from a real division

Check your understanding

Why is it safe to return the first path found rather than searching for a shortest or all paths?

PyPython 3 · solution.py

Optimal

1class Solution:2    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:3        from collections import defaultdict4        graph = defaultdict(dict)5        for (a, b), v in zip(equations, values):6            graph[a][b] = v7            graph[b][a] = 1.0 / v89        def dfs(src: str, dst: str, visited: set) -> float:10            if src not in graph or dst not in graph:11                return -1.012            if src == dst:13                return 1.014            visited.add(src)15            for nei, w in graph[src].items():16                if nei in visited:17                    continue18                res = dfs(nei, dst, visited)19                if res != -1.0:20                    return w * res21            return -1.02223        return [dfs(a, b, set()) for a, b in queries]

Time complexityO(q * (V + E))Optimized

Space complexityO(V + E)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

GoogleAmazonMeta

Evaluate Division

Evaluate Division

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Graph DFS and BFS