399. Evaluate Division - Detailed Explanation

Problem Statement

Description:
You are given a list of equations, where each equation is in the form a / b = k, represented by two strings (for the variables) and a real number k (for the value). You are also given some queries, where each query asks for the result of dividing one variable by another. Your task is to return the answers for all queries. If a query cannot be computed (e.g., the variable is unknown or the two variables are not connected), return -1.0 for that query.

Constraints:

• 1 ≤ equations.length ≤ 20

• 1 ≤ queries.length ≤ 20

• Each equation is given as a pair of strings and a corresponding real number.

• Variables are represented by strings consisting of lowercase English letters.

• The answer within 10^-5 of the actual value is acceptable.

Example 1:

• 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]
• Explanation:
  • "a / c": We can compute it as a / b * b / c = 2.0 * 3.0 = 6.0.
  • "b / a": The inverse of "a / b" gives 1/2.0 = 0.5.
  • "a / e": Since variable "e" does not exist, return -1.0.
  • "a / a": Any variable divided by itself is 1.0.
  • "x / x": Since variable "x" does not exist, return -1.0.

Example 2:

• Input:

  equations = [["x1","x2"], ["x2","x3"], ["x3","x4"], ["x4","x5"]]
  values = [3.0, 4.0, 5.0, 6.0]
  queries = [["x1","x5"], ["x5","x2"], ["x2","x4"], ["x2","x2"], ["x2","x9"]]
  

• Output: [360.0, 1/120.0, 20.0, 1.0, -1.0]
  (Note: 1/120.0 is approximately 0.00833.)

Hints to Approach the Problem

• Hint 1: Think of the equations as defining a weighted graph, where each variable is a node. An edge from node A to node B has a weight equal to the division value A/B. The reverse edge from B to A will have a weight of 1/(A/B).

• Hint 2: For each query, you can perform a graph traversal (e.g., depth-first search or breadth-first search) from the numerator variable to the denominator variable while multiplying the weights along the path.

• Hint 3: Alternatively, consider a Union-Find (Disjoint Set Union) approach where each union operation links two variables and maintains the division ratio between the parent and child.

• Hint 4: If either variable in the query is not in the graph, the result should be -1.0.

Approaches

DFS / BFS Graph Traversal

Idea:

• Build a graph from the equations. For every equation a / b = k, add an edge from a to b with weight k and an edge from b to a with weight 1/k.
• For each query, if both variables exist, perform DFS (or BFS) to find a path from the source to the target. Multiply the weights along the path to get the result.
• If no path exists, return -1.0.

Steps:

1. Create a mapping (graph) where each key is a variable and its value is a list of tuples: (neighbor, weight).

2. For each equation, add two directed edges.

3. For each query, initialize a visited set and perform DFS/BFS:

   • If you reach the target, return the cumulative product of weights.
   • If you exhaust the search without reaching the target, return -1.0.

Union-Find (Disjoint Set Union) with Weight Tracking

Idea:

• Each variable is a node. The union-find data structure groups connected variables together.
• When unioning two variables, store the ratio between them.
• For a query, if the two variables are in the same connected component, compute the ratio using the stored weights; otherwise, return -1.0.

Steps:

1. Initialize a parent mapping and a weight mapping (each variable’s weight relative to its parent).

2. For every equation a / b = k, union a and b appropriately.

3. For each query, if both variables exist and share the same root, compute the result as the ratio of their weights.

Note: The DFS approach is more intuitive for many, while the union-find approach is optimal for multiple queries on a static graph.

Detailed Walkthrough (DFS Approach)

Consider Example 1:
Equations: a / b = 2.0, b / c = 3.0
Graph representation:

• "a" connects to "b" with weight 2.0
• "b" connects to "a" with weight 0.5
• "b" connects to "c" with weight 3.0
• "c" connects to "b" with weight 1/3.0

For query "a" / "c":

1. Start at "a" with an initial product of 1.0.
2. Visit "a"'s neighbor "b"; product becomes 1.0 * 2.0 = 2.0.
3. From "b", visit "c"; product becomes 2.0 * 3.0 = 6.0.
4. Since "c" is reached, the answer is 6.0.

For query "b" / "a":

1. Start at "b"; product is 1.0.
2. From "b", visit "a" directly with weight 0.5; product becomes 1.0 * 0.5 = 0.5.
3. Answer is 0.5.

If a query involves a variable not in the graph (like "e") or the source and target are disconnected, return -1.0.

Code Implementation

Python Code