Watch the video solution for Unit Conversion II, a medium level problem involving Array, Math, Depth-First Search. This walkthrough by Code-Yao has 207 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
There are n types of units indexed from 0 to n - 1.
You are given a 2D integer array conversions of length n - 1, where conversions[i] = [sourceUniti, targetUniti, conversionFactori]. This indicates that a single unit of type sourceUniti is equivalent to conversionFactori units of type targetUniti.
You are also given a 2D integer array queries of length q, where queries[i] = [unitAi, unitBi].
Return an array answer of length q where answer[i] is the number of units of type unitBi equivalent to 1 unit of type unitAi, and can be represented as p/q where p and q are coprime. Return each answer[i] as pq-1 modulo 109 + 7, where q-1 represents the multiplicative inverse of q modulo 109 + 7.
Example 1:
Input: conversions = [[0,1,2],[0,2,6]], queries = [[1,2],[1,0]]
Output: [3,500000004]
Explanation:
conversions[0], then conversions[1].conversions[0]. We return 500000004 since it is the multiplicative inverse of 2.
Example 2:
Input: conversions = [[0,1,2],[0,2,6],[0,3,8],[2,4,2],[2,5,4],[3,6,3]], queries = [[1,2],[0,4],[6,5],[4,6],[6,1]]
Output: [3,12,1,2,83333334]
Explanation:
conversions[0], then conversions[1].conversions[1], then conversions[3].conversions[5], the inverse of conversions[2], conversions[1], then conversions[4].conversions[3], the inverse of conversions[1], conversions[2], then conversions[5].conversions[5], the inverse of conversions[2], then conversions[0]. We return 83333334 since it is the multiplicative inverse of 12.
Constraints:
2 <= n <= 105conversions.length == n - 10 <= sourceUniti, targetUniti < n1 <= conversionFactori <= 1091 <= q <= 105queries.length == q0 <= unitAi, unitBi < nProblem Overview: You are given relationships that define how one unit converts to another. Each conversion acts like an edge with a multiplier. The task is to determine the correct conversion value between units by chaining these relationships together.
Approach 1: Graph Modeling + DFS Traversal (O(V + E) per query time, O(V + E) space)
Treat each unit as a node in a weighted graph. A conversion like a → b = k becomes two edges: a → b (k) and b → a (1/k). To compute a requested conversion, run a depth-first search from the source unit and multiply weights along the path until the destination is reached. This works because any valid conversion chain forms a path in the graph. DFS is simple to implement with recursion and performs well for sparse graphs.
Approach 2: Breadth-First Search Path Evaluation (O(V + E) per query time, O(V + E) space)
The graph construction remains the same, but traversal uses a queue instead of recursion. Starting from the source unit, push neighbors into a queue while tracking the cumulative conversion multiplier. The first time you reach the target unit, the accumulated product gives the result. Breadth-first search is often preferred when you want predictable iteration without recursion depth concerns. The algorithm scans neighbors level by level until the conversion path is found.
Approach 3: Component Precomputation with DFS (O(V + E) preprocessing, O(1) queries, O(V + E) space)
If many conversions must be answered, precompute relative values for every node within a connected component. Pick an arbitrary root unit and run DFS to assign each unit a value relative to that root. Once stored, any conversion between two units in the same component is simply the ratio of their stored values. This converts repeated graph traversals into constant-time lookups after a single traversal.
Recommended for interviews: The adjacency list graph with DFS is the expected solution. It demonstrates correct modeling of multiplicative relationships and efficient traversal using graph techniques. Candidates often start with DFS, then discuss BFS as an alternative using breadth-first search or depth-first search. The key insight is recognizing that unit relationships form a weighted graph where conversions correspond to path multiplication.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Graph + DFS traversal | O(V + E) per query | O(V + E) | General solution when queries are limited and recursion is acceptable |
| Graph + BFS traversal | O(V + E) per query | O(V + E) | Preferred when avoiding recursion depth or when using iterative traversal |
| Component precomputation | O(V + E) preprocessing, O(1) per query | O(V + E) | Best when the graph is static and many conversion queries must be answered quickly |