Problem Description

You have n different types of units, numbered from 0 to n - 1. You're given conversion relationships between these units in a 2D array called conversions with length n - 1.

Each element in conversions is formatted as [sourceUnit_i, targetUnit_i, conversionFactor_i], which means:

• 1 unit of type sourceUnit_i equals conversionFactor_i units of type targetUnit_i

Your task is to find how many units of each type are equivalent to 1 unit of type 0 (the base unit).

Return an array baseUnitConversion of length n where:

• baseUnitConversion[i] represents how many units of type i equal 1 unit of type 0
• Since the numbers can be very large, return each value modulo 10^9 + 7

The problem guarantees that unit 0 can be converted to any other unit through a unique conversion path, forming a tree structure with unit 0 as the root. The conversion relationships create a connected graph where you can reach any unit from unit 0 through the given conversions.

For example, if unit 0 converts to unit 1 with factor 3, then 1 unit of type 0 equals 3 units of type 1, so baseUnitConversion[1] = 3.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The problem involves units (nodes) and conversion relationships (edges) between them. Each conversion [sourceUnit, targetUnit, conversionFactor] represents a directed edge from sourceUnit to targetUnit.

Is it a tree?

• Yes: The problem states that there are n units and n-1 conversion relationships, and unit 0 can reach any other unit through a unique conversion path. This describes a tree structure with unit 0 as the root.

DFS

• Yes: Since we have identified this as a tree problem, DFS is the appropriate algorithm to traverse from the root (unit 0) to all other nodes, calculating the conversion factors along the way.

Conclusion: The flowchart suggests using DFS (Depth-First Search) for this problem. Starting from unit 0 with a conversion factor of 1, we traverse the tree using DFS, multiplying the conversion factors along each path to compute how many units of each type equal 1 unit of type 0.

Intuition

Since we need to find how many units of each type equal 1 unit of type 0, we can think of this as finding the "distance" or "conversion factor" from the root (unit 0) to every other unit in the tree.

The key insight is that when we have a conversion like "1 unit of A equals 5 units of B", and we know that "1 unit of type 0 equals 3 units of A", then we can deduce that "1 unit of type 0 equals 3 × 5 = 15 units of B". This multiplication property naturally suggests a traversal approach where we accumulate the conversion factors as we move through the tree.

Since the problem guarantees a tree structure (n units with n-1 edges and unique paths), we don't need to worry about cycles or multiple paths to the same unit. This makes DFS a perfect fit - we can start from unit 0 with a conversion factor of 1, and as we traverse to each child unit, we multiply the current conversion factor by the edge's conversion factor.

For example, if we're at unit s with accumulated conversion factor mul (meaning 1 unit of type 0 = mul units of type s), and there's an edge from s to t with conversion factor w, then we know that 1 unit of type 0 equals mul × w units of type t.

The modulo operation (10^9 + 7) is applied during multiplication to prevent integer overflow, as the conversion factors can become very large when multiplied along a path.

Learn more about Depth-First Search, Breadth-First Search and Graph patterns.

Solution Approach

The implementation uses DFS with an adjacency list representation of the tree structure.

Building the Graph: First, we create an adjacency list g where g[i] stores all the units that unit i can convert to, along with their conversion factors. We iterate through the conversions array and for each conversion [s, t, w], we add (t, w) to g[s]. This creates a directed tree rooted at unit 0.

DFS Traversal: We define a recursive function dfs(s, mul) where:

• s is the current unit we're visiting
• mul is the accumulated conversion factor from unit 0 to unit s

The DFS function works as follows:

1. Store the conversion factor for the current unit: ans[s] = mul
2. For each child unit t with conversion factor w in g[s]:
   • Recursively call dfs(t, mul * w % mod)
   • The new conversion factor is mul * w because if 1 unit of type 0 = mul units of type s, and 1 unit of type s = w units of type t, then 1 unit of type 0 = mul * w units of type t

Initialization and Execution:

• Set mod = 10^9 + 7 for modulo operations
• Initialize n = len(conversions) + 1 (total number of units)
• Create the adjacency list g with n empty lists
• Initialize the answer array ans with zeros
• Start DFS from unit 0 with initial conversion factor 1: dfs(0, 1)

The algorithm has a time complexity of O(n) since we visit each unit exactly once in the tree traversal, and space complexity of O(n) for the adjacency list and recursion stack.

Example Walkthrough

Let's walk through a small example with 4 units (0, 1, 2, 3) and the following conversions:

• [0, 1, 2]: 1 unit of type 0 = 2 units of type 1
• [0, 2, 3]: 1 unit of type 0 = 3 units of type 2
• [1, 3, 5]: 1 unit of type 1 = 5 units of type 3

Step 1: Build the adjacency list

g[0] = [(1, 2), (2, 3)]  // unit 0 converts to units 1 and 2
g[1] = [(3, 5)]          // unit 1 converts to unit 3
g[2] = []                // unit 2 has no outgoing conversions
g[3] = []                // unit 3 has no outgoing conversions

Step 2: Start DFS from unit 0 with conversion factor 1

dfs(0, 1):

• Set ans[0] = 1 (1 unit of type 0 = 1 unit of type 0)
• Process children of unit 0:
  • Child 1 with factor 2: Call dfs(1, 1 * 2 = 2)
  • Child 2 with factor 3: Call dfs(2, 1 * 3 = 3)

dfs(1, 2):

• Set ans[1] = 2 (1 unit of type 0 = 2 units of type 1)
• Process children of unit 1:
  • Child 3 with factor 5: Call dfs(3, 2 * 5 = 10)

dfs(3, 10):

• Set ans[3] = 10 (1 unit of type 0 = 10 units of type 3)
• No children, return

dfs(2, 3):

• Set ans[2] = 3 (1 unit of type 0 = 3 units of type 2)
• No children, return

Final Result: ans = [1, 2, 3, 10]

This means:

• 1 unit of type 0 = 1 unit of type 0
• 1 unit of type 0 = 2 units of type 1
• 1 unit of type 0 = 3 units of type 2
• 1 unit of type 0 = 10 units of type 3

Note how unit 3 gets its conversion factor by multiplying along the path: 1 (starting) × 2 (0→1) × 5 (1→3) = 10.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm performs a depth-first search (DFS) starting from node 0. Each node is visited exactly once during the DFS traversal. For each node visited, we iterate through its adjacent nodes in the graph. Since we're building the graph from the conversions list which has n-1 edges (where n is the total number of units), and each edge is processed once during graph construction and once during DFS traversal, the total time complexity is O(n).

Space Complexity: O(n)

The space complexity consists of:

• The graph g which stores adjacency lists for n nodes: O(n) space
• The answer array ans which stores results for n nodes: O(n) space
• The recursive call stack for DFS which in the worst case (when the graph forms a chain) can go up to depth n: O(n) space

Therefore, the overall space complexity is O(n), where n is the number of units.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Apply Modulo During Multiplication

The Pitfall: One of the most common mistakes is forgetting to apply the modulo operation during the multiplication step in the DFS traversal. Developers often write:

# INCORRECT - can cause integer overflow
new_factor = cumulative_factor * conversion_ratio
dfs(target_unit, new_factor % MOD)

or even worse:

# INCORRECT - no modulo at all
new_factor = cumulative_factor * conversion_ratio
dfs(target_unit, new_factor)

Why This is Problematic:

• Python handles arbitrarily large integers, but the multiplication can still create extremely large intermediate values that slow down computation
• In other languages, this would cause integer overflow
• The final result after all multiplications might exceed the maximum value before applying modulo

The Solution: Always apply modulo immediately after multiplication:

# CORRECT
new_factor = (cumulative_factor * conversion_ratio) % MOD
dfs(target_unit, new_factor)

2. Building a Bidirectional Graph Instead of a Directed Tree

The Pitfall: Since the problem mentions that units can be converted between each other, developers might mistakenly build a bidirectional graph:

# INCORRECT - creates cycles
for source_unit, target_unit, conversion_ratio in conversions:
    adjacency_list[source_unit].append((target_unit, conversion_ratio))
    adjacency_list[target_unit].append((source_unit, 1/conversion_ratio))  # Wrong!

Why This is Problematic:

• Creates cycles in the graph, causing infinite recursion in DFS
• The problem specifically states the structure forms a tree with unit 0 as root
• The inverse conversion ratio (1/conversion_ratio) would be incorrect for the problem's requirements

The Solution: Build a directed tree following the exact conversion relationships given:

# CORRECT - directed tree from source to target only
for source_unit, target_unit, conversion_ratio in conversions:
    adjacency_list[source_unit].append((target_unit, conversion_ratio))

3. Incorrect Initialization of Base Unit

The Pitfall: Forgetting to set the correct initial conversion factor for unit 0:

# INCORRECT - unit 0 should have conversion factor 1
dfs(0, 0)  # Starting with 0 will make all conversions 0

Why This is Problematic:

• Unit 0 is the base unit, so 1 unit of type 0 equals 1 unit of type 0
• Starting with 0 would propagate 0 to all other units
• The result would be an array of all zeros

The Solution: Always start the DFS with conversion factor 1 for the base unit:

# CORRECT
dfs(0, 1)  # 1 unit of type 0 = 1 unit of type 0