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.
Return an array baseUnitConversion of length n, where baseUnitConversion[i] is the number of units of type i equivalent to a single unit of type 0. Since the answer may be large, return each baseUnitConversion[i] modulo 109 + 7.
Example 1:
Input: conversions = [[0,1,2],[1,2,3]]
Output: [1,2,6]
Explanation:
conversions[0].conversions[0], then conversions[1].
Example 2:
Input: conversions = [[0,1,2],[0,2,3],[1,3,4],[1,4,5],[2,5,2],[4,6,3],[5,7,4]]
Output: [1,2,3,8,10,6,30,24]
Explanation:
conversions[0].conversions[1].conversions[0], then conversions[2].conversions[0], then conversions[3].conversions[1], then conversions[4].conversions[0], conversions[3], then conversions[5].conversions[1], conversions[4], then conversions[6].
Constraints:
2 <= n <= 105conversions.length == n - 10 <= sourceUniti, targetUniti < n1 <= conversionFactori <= 109Problem Overview: You are given relationships between different measurement units (for example, 1 meter = 100 centimeter). The task is to determine conversion values between units that may not be directly connected. Think of each unit as a node and each conversion as a weighted edge that represents the multiplication factor between them.
Approach 1: Graph Traversal with DFS (O(V + E) per query time, O(V + E) space)
Model the problem as a weighted graph. Each unit becomes a node, and each conversion rule adds two directed edges: A -> B with weight w and B -> A with weight 1/w. When you need to compute a conversion between two units, run a depth-first search starting from the source unit and multiply edge weights along the path. A visited set prevents cycles. The key insight is that chained conversions correspond to multiplying weights along a path in the graph. DFS works well because you only need one valid path to compute the result.
This approach naturally fits problems involving graph traversal. The adjacency list stores neighbors and weights, and recursion explores reachable units until the destination is found. Each query explores at most all vertices and edges in the connected component.
Approach 2: Breadth-First Search Traversal (O(V + E) per query time, O(V + E) space)
The same graph structure can be traversed using a queue instead of recursion. Start from the source unit with an accumulated conversion factor of 1. For each neighbor, multiply the current factor by the edge weight and push the result into the queue. Once the target unit is reached, the accumulated product gives the conversion value. BFS guarantees the shortest number of edges explored first, though for multiplicative conversions any valid path works.
BFS is often preferred when recursion depth may become large or when you want an iterative solution. It still uses an adjacency list and a visited set, making it a standard application of breadth-first search and depth-first search patterns on graphs.
Recommended for interviews: The DFS graph approach is typically expected. Start by explaining the graph modeling step—units as nodes and conversion ratios as weighted edges. Show that multiplying weights along a path produces the correct conversion. BFS is an equally valid alternative, but DFS usually leads to a simpler implementation. Demonstrating both shows strong understanding of graph traversal techniques.
Since the problem guarantees that unit 0 can be converted to any other unit through a unique conversion path, we can use Depth-First Search (DFS) to traverse all unit conversion relationships. Additionally, since the length of the conversions array is n - 1, representing n - 1 conversion relationships, we can treat the unit conversion relationships as a tree, where the root node is unit 0, and the other nodes are the other units.
We can use an adjacency list g to represent the unit conversion relationships, where g[i] represents the units that unit i can convert to and the corresponding conversion factors.
Then, we start the DFS from the root node 0, i.e., call the function dfs(s, mul), where s represents the current unit, and mul represents the conversion factor from unit 0 to unit s. Initially, s = 0, mul = 1. In each recursion, we store the conversion factor mul of the current unit s into the answer array, then traverse all adjacent units t of the current unit s, and recursively call dfs(t, mul times w \mod (10^9 + 7)), where w is the conversion factor from unit s to unit t.
Finally, we return the answer array.
The complexity is O(n), and the space complexity is O(n), where n is the number of units.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS Graph Traversal | O(V + E) per query | O(V + E) | Standard solution for weighted conversion graphs |
| BFS Graph Traversal | O(V + E) per query | O(V + E) | Iterative traversal when avoiding recursion depth issues |
3528. Unit Conversion I (Leetcode Medium) • Programming Live with Larry • 313 views views
Watch 1 more video solutions →Practice Unit Conversion I with our built-in code editor and test cases.
Practice on FleetCode