#3528

Medium

auto_awesomeGraph traversal with depth-first search

LeetCode Problem Workspace

Unit Conversion I

Solve the unit conversion problem by using graph traversal to compute equivalent unit amounts.

depth first search breadth first search graph

Problem Statement

You are given a set of units indexed from 0 to n - 1, and a list of conversions between them. Each conversion is represented as an array of three integers: [sourceUniti, targetUniti, conversionFactori], which indicates that a single unit of sourceUniti is equivalent to conversionFactori units of targetUniti.

Your goal is to compute the conversion factor of each unit in relation to unit 0. Return an array where each entry represents the number of units of type i equivalent to a single unit of type 0, using depth-first search to traverse the conversion graph. The results should be modulo 10^9 + 7.

Examples

Example 1

Input: conversions = [[0,1,2],[1,2,3]]

Output: [1,2,6]

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]

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.

Solution Approach

Graph Construction

Represent the unit conversions as a directed, weighted graph. Each node in the graph represents a unit, and each edge represents a conversion between units. The edge weight is the conversion factor.

DFS Traversal

Apply a Depth-First Search (DFS) starting from unit 0. During the DFS, multiply the conversion factors along the path, and store the result for each unit in the result array. Use modular arithmetic to handle large numbers.

Modulo Operation

Since the output could be large, every result should be returned modulo 10^9 + 7. This ensures that the result fits within the expected range and prevents overflow.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time and space complexity depend on the graph traversal approach used. For DFS, the time complexity is O(n) where n is the number of units, and space complexity is O(n) due to the graph and recursion stack.

What Interviewers Usually Probe

The candidate's ability to identify graph traversal as the solution approach will be key.
Look for their understanding of Depth-First Search as it applies to this problem's structure.
Candidates should demonstrate an understanding of modular arithmetic when handling large numbers in the output.

Common Pitfalls or Variants

Common pitfalls

Not correctly using modulo 10^9 + 7, leading to overflow.
Misunderstanding the conversion relationships between units and failing to propagate conversion factors through the graph.
Not handling recursion depth properly in DFS or running into stack overflow for large inputs.

Follow-up variants

Adjusting the problem to handle bidirectional conversions between units.
Expanding the problem to handle more complex graph structures with cycles.
Optimizing for space and time complexity when the number of units is very large.

FAQ

How do I approach the 'Unit Conversion I' problem?

Focus on representing the units and conversions as a graph. Use DFS to traverse the graph and compute the conversion factor for each unit with respect to the base unit.

What pattern is most useful for solving the 'Unit Conversion I' problem?

Graph traversal using Depth-First Search (DFS) is the key pattern to solve this problem. The problem is essentially about finding paths in a weighted directed tree.

Why do we need to use modulo in 'Unit Conversion I'?

Modulo 10^9 + 7 is used to prevent overflow since the conversion factors can become very large. It ensures that the output fits within the constraints.

What is the best way to represent the conversions in 'Unit Conversion I'?

Use an adjacency list to represent the graph, where each node corresponds to a unit, and the edges store the conversion factors between units.

How does DFS help in solving 'Unit Conversion I'?

DFS allows you to traverse the graph starting from unit 0 and calculate the conversion factor for each unit by multiplying the conversion factors along the path.

terminal

Solution

Solution 1: DFS

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 $\textit{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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

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

Continue Practicing

#3493 properties graph #3607 power grid maintenance #3419 minimize the maximum edge weight of graph