Evaluate Division

Q: 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.

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).

Q: 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.

Medium DFS

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

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. This approach efficiently handles cycles and disconnected components by tracking visited nodes.

Optimal Approach

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.

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.

Pattern Spotlight

DFS (Graph Traversal with Accumulated State)

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.

Solution

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

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.

Perform DFS to Compute Division Result for Each Query

13def dfs(node, target, curr, visited):
  if node == target:
      return curr
  visited.add(node)
  for nei, weight in graph[node]:
      if nei not in visited:
          res = dfs(nei, target, curr * weight, visited)
          if res != -1:
              return res
  return -1

Objective

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

Key Insight

DFS explores all possible paths from the start variable to the target, multiplying edge weights to compute the division result. Tracking visited nodes prevents infinite loops in cyclic graphs. Returning the accumulated product upon reaching the target ensures correct evaluation of indirect relationships.

Interview Quick-Check

Core Logic

DFS recursively multiplies edge weights along the path and returns the product when the target node is reached.

State & Boundaries

Visited nodes are tracked to avoid cycles and redundant exploration.

Common Pitfalls & Bugs

Failing to return -1 when no path exists or not handling visited nodes leads to incorrect or infinite recursion.

Handle Queries by Validating Variables and Invoking DFS

28res = []
30for a, b in queries:
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()))
37return res

Objective

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

Key Insight

Queries involving unknown variables cannot be resolved and immediately return -1. For valid variables, invoking DFS with an initial product of 1 and an empty visited set computes the division result. This separation of concerns ensures correctness and efficiency.

Interview Quick-Check

Core Logic

Check if both variables exist in the graph before DFS to avoid unnecessary computation.

State & Boundaries

Initialize DFS with product 1 and empty visited set for each query.

Common Pitfalls & Bugs

Not handling missing variables leads to incorrect results or runtime errors.

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.

Line 22 Critical

res = dfs(nei, target, curr * weight, visited)

Recursively call DFS on the neighbor, updating the product with the edge weight.

Multiplying the current product by the edge weight accumulates the division value along the path.

Line 26 Critical

return -1

Return -1 if no path to target was found from the current node.

Returning -1 signals failure to find a valid division path, allowing callers to handle missing relationships.

Line 35 Critical

res.append(dfs(a, b, 1, set()))

Invoke DFS to compute the division result for valid queries and append it to the result list.

Calling DFS with initial product 1 and empty visited set computes the correct division value or -1 if no path exists.

Line 10 Core

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

Add an edge from variable a to b with weight val.

This encodes the division a / b = val as a directed edge in the graph, enabling traversal from a to b.

Line 18 Core

visited.add(node)

Mark the current node as visited to avoid cycles.

Tracking visited nodes prevents infinite recursion and redundant exploration in cyclic graphs.

Line 21 Core

if nei not in visited:

Check if the neighbor has not been visited yet.

Avoiding revisiting nodes prevents cycles and infinite recursion.

Line 23 Core

if res != -1:

Check if the recursive DFS call found a valid result.

A result different from -1 indicates a successful path to the target was found.

Line 24 Core

return res

Return the valid result immediately to terminate search.

Returning early upon finding a valid path improves efficiency by avoiding unnecessary exploration.

Line 32 Core

if a not in graph or b not in graph:

Check if either variable in the query is missing from the graph.

Queries involving unknown variables cannot be resolved and must return -1 immediately.

Line 4 Core

graph = defaultdict(list)

Initialize a default dictionary to represent the graph as adjacency lists.

Using a defaultdict of lists allows efficient insertion of edges without predefining keys, simplifying graph construction.

Line 13 Core

def dfs(node, target, curr, visited):

Define a recursive DFS function to find the product path from node to target.

Encapsulating DFS logic in a helper function enables clean recursive traversal with accumulated product and visited tracking.

Line 20 Core

for nei, weight in graph[node]:

Iterate over neighbors and their edge weights of the current node.

Exploring all adjacent nodes is necessary to find a path to the target and accumulate the product of weights.

Line 33 Core

res.append(-1)

Append -1 to the result list for invalid queries.

This handles queries with missing variables by returning the specified failure value.

Line 34 Core

else:

Invoke DFS only for valid queries where both variables exist in the graph.

The else branch ensures DFS is only executed when both variables exist in the graph. This avoids unnecessary traversal and guarantees that DFS operates on valid nodes, since queries involving unknown variables have already been handled by returning -1.

Line 37 Standard

return res

Return the list of results for all queries.

Returning the accumulated results completes the function and provides the final output.

Line 6 Standard

for i in range(len(equations)):

Iterate over all given equations by index.

Looping through equations and values in parallel enables building the graph edges for each equation.

Line 28 Standard

res = []

Initialize the result list to store answers for all queries.

Collecting results in a list enables returning all query answers in the required format.

Line 30 Standard

for a, b in queries:

Iterate over each query pair (a, b).

Processing queries sequentially allows independent evaluation of each division request.

Line 7 Standard

a, b = equations[i]

Extract the two variables from the current equation.

Separating variables a and b clarifies the direction of edges to be added to the graph.

Line 8 Standard

val = values[i]

Retrieve the division value corresponding to the current equation.

This value represents the weight of the edge from a to b in the graph.

Test Your Understanding

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

Because the division relationships form a graph where the value of a query depends on the product of edge weights along a path between variables. Direct lookup is insufficient when variables are connected indirectly. DFS explores all possible paths while avoiding cycles by tracking visited nodes, ensuring correct and efficient computation.

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`

Problem

Example

Approach

Solution

Step-by-Step Solution

Build a Bidirectional Weighted Graph Representing Division Relations

Perform DFS to Compute Division Result for Each Query

Handle Queries by Validating Variables and Invoking DFS

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.