Unit Conversion II - Video Solutions
leetcode 3535 Unit Conversion II | dfs or bfs, mod multiplicative inverse
Unit Conversion II - Video Solution
Watch the video solution for Unit Conversion II, a medium level problem involving Array, Math, Depth-First Search. This walkthrough by Code-Yao has 233 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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:
- In the first query, we can convert unit 1 into 3 units of type 2 using the inverse of
conversions[0], thenconversions[1]. - In the second query, we can convert unit 1 into 1/2 units of type 0 using the inverse of
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:
- In the first query, we can convert unit 1 into 3 units of type 2 using the inverse of
conversions[0], thenconversions[1]. - In the second query, we can convert unit 0 into 12 units of type 4 using
conversions[1], thenconversions[3]. - In the third query, we can convert unit 6 into 1 unit of type 5 using the inverse of
conversions[5], the inverse ofconversions[2],conversions[1], thenconversions[4]. - In the fourth query, we can convert unit 4 into 2 units of type 6 using the inverse of
conversions[3], the inverse ofconversions[1],conversions[2], thenconversions[5]. - In the fifth query, we can convert unit 6 into 1/12 units of type 1 using the inverse of
conversions[5], the inverse ofconversions[2], thenconversions[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 < n- It is guaranteed that unit 0 can be uniquely converted into any other unit through a combination of forward or backward conversions.
Approach Overview
Problem 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.
Complexity Analysis
| 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 |