# Unit Conversion I
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/unit-conversion-i)
Canonical: https://scaleengineer.com/dsa/problems/unit-conversion-i
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Graph
---
## Problem
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:**

* Convert a single unit of type 0 into 2 units of type 1 using `conversions[0]`.
* Convert a single unit of type 0 into 6 units of type 2 using `conversions[0]`, then `conversions[1]`.
![](https://assets.glich.co/dsa/unit-conversion-i/image0.png)

**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:**

* Convert a single unit of type 0 into 2 units of type 1 using `conversions[0]`.
* Convert a single unit of type 0 into 3 units of type 2 using `conversions[1]`.
* Convert a single unit of type 0 into 8 units of type 3 using `conversions[0]`, then `conversions[2]`.
* Convert a single unit of type 0 into 10 units of type 4 using `conversions[0]`, then `conversions[3]`.
* Convert a single unit of type 0 into 6 units of type 5 using `conversions[1]`, then `conversions[4]`.
* Convert a single unit of type 0 into 30 units of type 6 using `conversions[0]`, `conversions[3]`, then `conversions[5]`.
* Convert a single unit of type 0 into 24 units of type 7 using `conversions[1]`, `conversions[4]`, then `conversions[6]`.

**Constraints:**

* `2 <= n <= 105`
* `conversions.length == n - 1`
* `0 <= sourceUniti, targetUniti < n`
* `1 <= conversionFactori <= 109`
* It is guaranteed that unit 0 can be converted into any other unit through a **unique** combination of conversions without using any conversions in the opposite direction.

# Approaches
## Brute Force using Repeated Graph Traversal
This approach tackles the problem by directly answering the question for each unit one by one. For every unit `i` (from 1 to `n-1`), we want to find the conversion factor from unit 0. We can achieve this by finding the path from unit 0 to unit `i` in the conversion graph and multiplying the factors along that path. A graph traversal algorithm like Breadth-First Search (BFS) or Depth-First Search (DFS) can be used to find this path. This entire process is repeated for all `n-1` units, leading to a lot of repeated work.
**Time:** O(n^2) - We iterate through `n-1` target units. For each unit, we perform a graph traversal (BFS/DFS) which takes O(V+E) = O(n) time in the worst case. This results in a total time complexity of O(n * n). · **Space:** O(n) - The adjacency list requires O(n) space. For each of the n-1 traversals, the queue and visited array also require O(n) space.
**Pros:** Conceptually simple and directly follows the problem's request for each unit.; Easy to implement without needing deeper graph theory insights.
**Cons:** Highly inefficient due to redundant computations. The same subpaths (e.g., from unit 0 to some intermediate unit) are traversed multiple times across the different searches.; Will likely result in a 'Time Limit Exceeded' error for large inputs due to its quadratic time complexity.
### Explanation
The algorithm proceeds as follows:
1.  First, we build a graph representation of the unit conversions. An adjacency list is a good choice, where for each conversion `[u, v, w]`, we add a directed edge from `u` to `v` with weight `w`.
2.  We initialize our result array, `baseUnitConversion`, of size `n`. We know `baseUnitConversion[0]` is 1.
3.  Then, we loop through every other unit `i` from 1 to `n-1`.
4.  Inside the loop, for each `i`, we start a fresh Breadth-First Search (BFS) from unit 0. The goal of this BFS is to find the path and the corresponding cumulative conversion factor to reach `i`.
5.  The BFS queue will store pairs of `[node, cumulativeFactor]`. We start by adding `[0, 1]` to the queue.
6.  When we explore from a node `u` with factor `F_u` to its neighbor `v` via an edge with weight `w`, the new cumulative factor for `v` is `(F_u * w) % MOD`.
7.  When our BFS reaches the target node `i`, we record its computed cumulative factor in `baseUnitConversion[i]` and can terminate that specific search.
8.  After iterating through all `i`, the `baseUnitConversion` array is complete and can be returned.

```java
import java.util.*;

class Solution {
    private static final int MOD = 1_000_000_007;

    public long[] unitConversion(int n, int[][] conversions) {
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] conv : conversions) {
            adj.get(conv[0]).add(new int[]{conv[1], conv[2]});
        }

        long[] baseUnitConversion = new long[n];
        baseUnitConversion[0] = 1;

        for (int i = 1; i < n; i++) {
            // For each target unit 'i', run a separate BFS from 0
            Queue<long[]> bfsQueue = new LinkedList<>(); // {node, cumulativeFactor}
            bfsQueue.offer(new long[]{0, 1});
            boolean[] visited = new boolean[n];
            visited[0] = true;

            while(!bfsQueue.isEmpty()){
                long[] current = bfsQueue.poll();
                int u = (int)current[0];
                long uFactor = current[1];

                if(u == i){
                    baseUnitConversion[i] = uFactor;
                    break; // Found the path to i, can stop this BFS
                }

                for(int[] edge : adj.get(u)){
                    int v = edge[0];
                    int factor = edge[1];
                    if(!visited[v]){
                        visited[v] = true;
                        long vFactor = (uFactor * factor) % MOD;
                        bfsQueue.offer(new long[]{v, vFactor});
                    }
                }
            }
        }
        return baseUnitConversion;
    }
}
```
### Algorithm
- **Build Graph:** Represent the conversions as a directed graph. An adjacency list is a suitable data structure, where `adj[u]` stores a list of pairs `(v, factor)`, indicating that `1 unit of u = factor units of v`.
- **Initialize Result:** Create an array `baseUnitConversion` of size `n`. Set `baseUnitConversion[0] = 1`.
- **Iterate and Search:** For each unit `i` from 1 to `n-1`:
  - Perform a graph traversal (e.g., BFS) starting from unit 0 to find unit `i`.
  - During the BFS, keep track of the cumulative conversion factor from the start node (0) to the current node.
  - When a node `u` with cumulative factor `F_u` is processed, and it has a neighbor `v` with conversion factor `w`, the cumulative factor for `v` is `(F_u * w) % MOD`.
  - Once unit `i` is found, its calculated cumulative factor is the answer. Store this in `baseUnitConversion[i]`.
- **Return Result:** Return the `baseUnitConversion` array.

## Optimal Solution using Single Graph Traversal (DFS/BFS)
This optimal approach leverages the key insight from the problem constraints: the `n` units and `n-1` conversions form a tree structure rooted at unit 0. This is because there are `n` nodes, `n-1` edges, and every node is reachable from node 0, which defines a tree. This structure guarantees a unique, directed path from unit 0 to every other unit. Instead of finding each path individually, we can find all of them simultaneously in a single graph traversal (either DFS or BFS) starting from the root (unit 0).
**Time:** O(n) - Building the adjacency list takes O(n) time. The single DFS or BFS traversal visits each of the `n` units and `n-1` conversions exactly once. Thus, the total time complexity is linear with respect to the number of units. · **Space:** O(n) - The adjacency list requires O(n) space to store the n-1 conversions. The result array also takes O(n). The queue for BFS or the recursion stack for DFS can take up to O(n) space in the worst case (a skewed tree).
**Pros:** Optimal time complexity, making it highly efficient and suitable for large constraints.; Elegant solution that correctly models the problem's underlying tree structure.; Avoids all redundant calculations by visiting each node and edge only once.
**Cons:** Requires the insight that the problem can be modeled as a tree traversal from a single root, which might not be immediately obvious.
### Explanation
The core idea is to perform one traversal that calculates the conversion factors for all units at once. We start at unit 0, whose conversion factor relative to itself is 1.

1.  **Graph Representation:** We first build an adjacency list from the `conversions` array. For each `[source, target, factor]`, we store an edge from `source` to `target` with the given `factor`.
2.  **Initialization:** We create our result array, `baseUnitConversion`, and set `baseUnitConversion[0] = 1`.
3.  **Single Traversal:** We can use either BFS or DFS.
    - **Using BFS:** We initialize a queue with the root node, 0. We then enter a loop that continues as long as the queue is not empty. In each step, we dequeue a unit `u`. We already know its conversion factor, `baseUnitConversion[u]`. For each of its children `v` (connected by a conversion with factor `w`), we can compute its conversion factor from unit 0 by extending the path from `u`. The new factor is `baseUnitConversion[v] = (baseUnitConversion[u] * w) % MOD`. We then enqueue `v` so that its children can be processed. Since it's a tree, we don't need a `visited` array; each node will be reached exactly once.
    - **Using DFS:** We can define a recursive function `dfs(u)`. We start by calling `dfs(0)`. Inside the function for node `u`, we iterate through its children `v`. For each child, we calculate its factor `baseUnitConversion[v]` based on `baseUnitConversion[u]` and the connecting factor, and then make a recursive call `dfs(v)`.

Both traversal methods ensure that every node and edge is visited exactly once, making the solution highly efficient.

**BFS Implementation:**
```java
import java.util.*;

class Solution {
    private static final int MOD = 1_000_000_007;

    public long[] unitConversion(int n, int[][] conversions) {
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] conv : conversions) {
            adj.get(conv[0]).add(new int[]{conv[1], conv[2]});
        }

        long[] baseUnitConversion = new long[n];
        baseUnitConversion[0] = 1;

        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);

        while (!queue.isEmpty()) {
            int u = queue.poll();

            for (int[] edge : adj.get(u)) {
                int v = edge[0];
                int factor = edge[1];
                
                baseUnitConversion[v] = (baseUnitConversion[u] * factor) % MOD;
                
                queue.offer(v);
            }
        }

        return baseUnitConversion;
    }
}
```
### Algorithm
- **Build Graph:** Construct an adjacency list representation of the directed graph from the `conversions` array. `adj[u]` will contain pairs of `(v, factor)`.
- **Initialize:** Create the `baseUnitConversion` array of size `n`. Initialize `baseUnitConversion[0] = 1`.
- **Single Traversal (BFS):**
  - Create a queue and add the root node, 0.
  - While the queue is not empty:
    - Dequeue the current unit, `u`.
    - For each neighbor `v` of `u` with conversion factor `w`:
      - Calculate `baseUnitConversion[v] = (baseUnitConversion[u] * w) % MOD`.
      - Enqueue the neighbor `v` to be processed later.
- **Single Traversal (DFS Alternative):**
  - Define a recursive function, say `calculateFactors(u)`.
  - Inside the function, iterate through all neighbors `v` of `u` with conversion factor `w`.
  - For each neighbor, calculate `baseUnitConversion[v] = (baseUnitConversion[u] * w) % MOD`.
  - Make a recursive call: `calculateFactors(v)`.
  - Start the process by setting `baseUnitConversion[0] = 1` and then calling `calculateFactors(0)`.
- **Return Result:** After the single traversal is complete, the `baseUnitConversion` array will be fully populated. Return it.

# Solutions
### Java

```java
class Solution {
private
  final int mod = (int)1 e9 + 7;
private
  List<int[]>[] g;
private
  int[] ans;
private
  int n;
public
  int[] baseUnitConversions(int[][] conversions) {
    n = conversions.length + 1;
    g = new List[n];
    Arrays.setAll(g, k->new ArrayList<>());
    ans = new int[n];
    for (var e : conversions) {
      g[e[0]].add(new int[]{e[1], e[2]});
    }
    dfs(0, 1);
    return ans;
  }
private
  void dfs(int s, long mul) {
    ans[s] = (int)mul;
    for (var e : g[s]) {
      dfs(e[0], mul * e[1] % mod);
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> baseUnitConversions(vector<vector<int>> &conversions) {
    const int mod = 1e9 + 7;
    int n = conversions.size() + 1;
    vector<vector<pair<int, int>>> g(n);
    vector<int> ans(n);
    for (const auto &e : conversions) {
      g[e[0]].push_back({e[1], e[2]});
    }
    auto dfs = [&](this auto &&dfs, int s, long long mul) -> void {
      ans[s] = mul;
      for (auto [t, w] : g[s]) {
        dfs(t, mul * w % mod);
      }
    };
    dfs(0, 1);
    return ans;
  }
};

```

### Python

```python
class Solution:
    def baseUnitConversions(self, conversions: List[List[int]]) -> List[int]: def dfs(s: int, mul: int) -> None: ans[s] = mul for t, w in g[s]: dfs(t, mul * w % mod) mod = 10 ** 9 + 7 n = len(conversions) + 1 g = [[] for _ in range(n)] for s, t, w in conversions: g[s]. append((t, w)) ans = [0] * n dfs(0, 1) return ans

```