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}