Unit Conversion I

• 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.

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.

1import java.util.*;2 3class Solution {4    private static final int MOD = 1_000_000_007;5 6    public long[] unitConversion(int n, int[][] conversions) {7        List<List<int[]>> adj = new ArrayList<>();8        for (int i = 0; i < n; i++) {9            adj.add(new ArrayList<>());10        }11        for (int[] conv : conversions) {12            adj.get(conv[0]).add(new int[]{conv[1], conv[2]});13        }14 15        long[] baseUnitConversion = new long[n];16        baseUnitConversion[0] = 1;17 18        for (int i = 1; i < n; i++) {19            // For each target unit 'i', run a separate BFS from 020            Queue<long[]> bfsQueue = new LinkedList<>(); // {node, cumulativeFactor}21            bfsQueue.offer(new long[]{0, 1});22            boolean[] visited = new boolean[n];23            visited[0] = true;24 25            while(!bfsQueue.isEmpty()){26                long[] current = bfsQueue.poll();27                int u = (int)current[0];28                long uFactor = current[1];29 30                if(u == i){31                    baseUnitConversion[i] = uFactor;32                    break; // Found the path to i, can stop this BFS33                }34 35                for(int[] edge : adj.get(u)){36                    int v = edge[0];37                    int factor = edge[1];38                    if(!visited[v]){39                        visited[v] = true;40                        long vFactor = (uFactor * factor) % MOD;41                        bfsQueue.offer(new long[]{v, vFactor});42                    }43                }44            }45        }46        return baseUnitConversion;47    }48}

• 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.

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:

1import java.util.*;2 3class Solution {4    private static final int MOD = 1_000_000_007;5 6    public long[] unitConversion(int n, int[][] conversions) {7        List<List<int[]>> adj = new ArrayList<>();8        for (int i = 0; i < n; i++) {9            adj.add(new ArrayList<>());10        }11        for (int[] conv : conversions) {12            adj.get(conv[0]).add(new int[]{conv[1], conv[2]});13        }14 15        long[] baseUnitConversion = new long[n];16        baseUnitConversion[0] = 1;17 18        Queue<Integer> queue = new LinkedList<>();19        queue.offer(0);20 21        while (!queue.isEmpty()) {22            int u = queue.poll();23 24            for (int[] edge : adj.get(u)) {25                int v = edge[0];26                int factor = edge[1];27                28                baseUnitConversion[v] = (baseUnitConversion[u] * factor) % MOD;29                30                queue.offer(v);31            }32        }33 34        return baseUnitConversion;35    }36}