How do you solve Evaluate Division?

Construct a bidirectional graph where each edge from a to b has weight val and from b to a has weight 1/val. For each query, if either variable is missing, return -1. Otherwise, perform DFS starting from the numerator, multiplying edge weights along the path until the denominator is reached or all paths are exhausted. Return the accumulated product or -1 if no path exists.

What pattern does Evaluate Division use?

The Pattern: DFS (Graph Traversal with Accumulated State) The Heuristic: When evaluating relationships expressed as ratios or products over variable pairs, model the problem as a weighted graph and use DFS to accumulate multiplicative weights along paths, carefully tracking visited nodes to avoid cycles and redundant computation.

Evaluate Division — DFS

Q: What is the time complexity of Evaluate Division?

O(Q * E) where Q is the number of queries and E is the number of edges in the graph. Building the graph takes O(E) time. Each DFS for a query explores at most all edges reachable from the start node, which is O(E). For Q queries, worst-case complexity is O(Q * E).

Problem

Given a list of equations in the form of variable pairs and their division results, and a list of queries, return the result of each query as the division of the two variables, or -1 if the division cannot be determined.

1 ≤ equations.length ≤ 20
equations[i].length == 2
1 ≤ values.length == equations.length ≤ 20
0.0 < values[i] ≤ 20.0
1 ≤ queries.length ≤ 20
queries[i].length == 2
Variables are strings of length between 1 and 5, consisting of lowercase English letters and digits.

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]

The equations imply a / b = 2.0 and b / c = 3.0. To find a / c, multiply a / b and b / c to get 6.0. For b / a, take the reciprocal of a / b, which is 0.5. Queries involving variables not in the graph (like 'e' or 'x') return -1.0. The query a / a returns 1.0 since any variable divided by itself is 1.

Approach

Straightforward Solution

A brute-force approach would attempt to evaluate each query by enumerating all possible paths between variables, which is inefficient and redundant, especially if repeated queries or cycles exist.

Core Observation

The problem can be modeled as a directed weighted graph where variables are nodes and edges represent division relationships with weights. The value of a query corresponds to the product of edge weights along a path from the numerator to the denominator.

Path to Optimal

Preview

Recognizing the problem as a graph traversal task, the key insight is to build a graph from the equations and perform a Depth-First Search (DFS) for each query to find a path from the numerator to the denominator, accumulating the product of edge weights along the path…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Construct a bidirectional graph where each edge from a to b has weight val and from b to a has weight 1/val. For each query, if either variable is missing, return -1…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(Q * E) where Q is the number of queries and E is the number of edges in the graph

Building the graph takes O(E) time. Each DFS for a query explores at most all edges reachable from the start node, which is O(E). For Q queries, worst-case complexity is O(Q * E).

Space

O(V + E)

The graph stores adjacency lists for each of the V variables with E edges. The recursion stack and visited set for DFS use O(V) space. This auxiliary space is necessary to represent the problem and perform traversal.

Solution

Python

1class Solution:
2    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
3
4        graph = defaultdict(list)
5
6        for i in range(len(equations)):
7            a, b = equations[i]
8            val = values[i]
9
10            graph[a].append((b, val))
11            graph[b].append((a, 1 / val))
12
13        def dfs(node, target, curr, visited):
14
15            if node == target:
16                return curr
17
18            visited.add(node)
19
20            for nei, weight in graph[node]:
21                if nei not in visited:
22                    res = dfs(nei, target, curr * weight, visited)
23                    if res != -1:
24                        return res
25
26            return -1
27
28        res = []
29
30        for a, b in queries:
31
32            if a not in graph or b not in graph:
33                res.append(-1)
34            else:
35                res.append(dfs(a, b, 1, set()))
36
37        return res

Step-by-Step Solution

1

Build a Bidirectional Weighted Graph Representing Division Relations

4graph = defaultdict(list)
6for i in range(len(equations)):
7    a, b = equations[i]
8    val = values[i]
10    graph[a].append((b, val))
11    graph[b].append((a, 1 / val))

Objective

To represent the given equations as a graph where each variable is a node and edges encode division values and their reciprocals.

Key Insight

Modeling the problem as a graph allows leveraging graph traversal algorithms to evaluate queries. Each equation a / b = val translates to two edges: a → b with weight val, and b → a with weight 1/val. This bidirectional representation captures the invertible nature of division and enables traversal in either direction.

Interview Quick-Check

Core Logic

Each equation adds two edges to the graph, ensuring that division and its reciprocal are both represented for traversal.

Common Pitfalls & Bugs

Forgetting to add the reciprocal edge leads to incomplete graph representation and incorrect query results.

State & Boundaries

The graph is built once before processing queries, enabling efficient repeated lookups.

2

Perform DFS to Compute Division Result for Each Query

To recursively search for a path between the numerator and denominator variables, accumulating the product of edge weights along the path.

3

Handle Queries by Validating Variables and Invoking DFS

To process each query by checking variable existence and using DFS to compute the division result or return -1 if impossible.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 6 Critical lines interviewers watch for.

Line 11 Critical

graph[b].append((a, 1 / val))

Add the reciprocal edge from b to a with weight 1/val.

Including the reciprocal edge captures the invertible nature of division, allowing traversal in both directions.

Line 15 Critical

if node == target:

Check if the current node is the target node.

Reaching the target node means the accumulated product is the division result for the query.

Line 16 Critical

return curr

Return the accumulated product when target is reached.

Returning the product here terminates recursion and propagates the correct division value up the call stack.

Full line-by-line criticality + rationale for all 23 lines available on Pro.

Test Your Understanding

Why is DFS with visited tracking necessary instead of a simple direct lookup for queries?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Evaluate Division from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Evaluate Division drill

or drill a free problem

4	`graph = defaultdict(list)`
6	`for i in range(len(equations)):`
7	`a, b = equations[i]`
8	`val = values[i]`
10	`graph[a].append((b, val))`
11	`graph[b].append((a, 1 / val))`

1	`class Solution:`
2	`def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:`
3
4	`graph = defaultdict(list)`
5
6	`for i in range(len(equations)):`
7	`a, b = equations[i]`
8	`val = values[i]`
9
10	`graph[a].append((b, val))`
11	`graph[b].append((a, 1 / val))`
12
13	`def dfs(node, target, curr, visited):`
14
15	`if node == target:`
16	`return curr`
17
18	`visited.add(node)`
19
20	`for nei, weight in graph[node]:`
21	`if nei not in visited:`
22	`res = dfs(nei, target, curr * weight, visited)`
23	`if res != -1:`
24	`return res`
25
26	`return -1`
27
28	`res = []`
29
30	`for a, b in queries:`
31
32	`if a not in graph or b not in graph:`
33	`res.append(-1)`
34	`else:`
35	`res.append(dfs(a, b, 1, set()))`
36
37	`return res`