Evaluate Division

Explanation & Solution

Description

You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single variable.

You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj.

Return the answers to all queries. If a single answer cannot be determined, return -1.0.

Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.

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]

0.5

-1

Explanation: Given: a / b = 2.0, b / c = 3.0. Queries are: a / c = (a/b) * (b/c) = 6.0, b / a = 1/(a/b) = 0.5, a / e = -1.0 (e is not defined), a / a = 1.0, x / x = -1.0 (x is not defined).

Constraints

1 <= equations.length <= 20
equations[i].length == 2
1 <= Ai.length, Bi.length <= 5
values.length == equations.length
0.0 < values[i] <= 20.0
1 <= queries.length <= 20
queries[j].length == 2
1 <= Cj.length, Dj.length <= 5
Ai, Bi, Cj, Dj consist of lower case English letters and digits

Approach

Graphs pattern

1. Build a Weighted Graph

Create an adjacency list using a Map
For each equation a / b = w, add two directed edges:
a → b with weight w
b → a with weight 1 / w
This captures both the forward and reverse relationships

2. Process Each Query with BFS

For each query [src, dst], perform a breadth-first search from src to dst
If either variable is not in the graph, immediately return -1.0
If src === dst, return 1.0 (any variable divided by itself is 1)

3. Traverse and Multiply Weights

Start BFS from src with an initial product of 1.0
At each step, multiply the running product by the edge weight to the neighbor
If we reach dst, return the accumulated product — this is the answer
Track visited nodes to avoid cycles

4. Handle Unreachable Variables

If BFS completes without finding dst, the variables are in disconnected components
Return -1.0 for that query

5. Collect All Results

Map over all queries, running BFS for each one
Return the array of results

Key Insight

Division relationships form a weighted graph — if a / b = 2 and b / c = 3, then the path a → b → c gives a / c = 2 * 3 = 6
Finding x / y is equivalent to finding a path from x to y and multiplying all edge weights along that path
BFS guarantees we explore the shortest path first, and the visited set prevents infinite loops

Time

**O(Q × (V + E))** where Q is the number of queries

Space

O(V + E) for the graph

Solution Code

Minimum Height Trees

Word Ladder