LeetCode 3528 - Unit Conversion I

Difficulty: 🟡 Medium
Topics: Depth-First Search, Breadth-First Search, Graph Theory

Solution

Problem Understanding

The problem is asking us to compute, for each unit type from 0 to n-1, the number of that unit equivalent to a single unit of type 0. We are given a list of direct conversion relationships between units. Each conversion specifies that 1 unit of sourceUnit is equivalent to some integer conversionFactor of targetUnit.

Essentially, the conversions form a tree rooted at unit 0, because it is guaranteed that there is a unique path from unit 0 to any other unit. This means there are no cycles and no ambiguities in conversions. Each unit can be reached from unit 0 through exactly one sequence of conversions. The task is to propagate the conversion factors along this tree to compute, for each unit, how many of that unit equals 1 unit of type 0, modulo 10^9 + 7 to handle large numbers.

The input constraints indicate that n can be as large as 10^5, and conversion factors can be as large as 10^9. A naive approach that multiplies conversion factors along all paths repeatedly would be inefficient. The guarantee of a unique path from 0 allows us to use a DFS or BFS traversal of the tree to compute the answer in linear time.

Important edge cases include when n=2 (minimum number of units), when some conversion factors are 1, and when the tree is deep or unbalanced.

Approaches

The brute-force approach would attempt to recursively compute the number of units for each target unit by exploring all paths from unit 0. This works for small input sizes but is inefficient because it repeatedly recomputes conversions along shared paths. With n up to 10^5, this would be too slow.

The key insight for an optimal solution is that the conversions form a tree with unit 0 as the root. Because each unit has a unique parent (from the conversion input), we can traverse the tree starting from 0, computing the conversion factor for each child as the conversion factor of its parent multiplied by the factor from the parent to the child. We only need a single DFS or BFS traversal to compute all conversions. Multiplying along the path gives the correct number of units, and we apply modulo 10^9 + 7 at each step to prevent integer overflow.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(n)	Recursively recompute conversions along paths; inefficient for large n
Optimal	O(n)	O(n)	Single DFS/BFS on tree; multiply conversion factors along the path from root

Algorithm Walkthrough

Initialize an adjacency list to represent the tree. Each node maps to a list of tuples (child, conversionFactor).
Create an array baseUnitConversion of length n and set baseUnitConversion[0] = 1 because 1 unit of type 0 equals itself.
Perform a DFS (or BFS) starting from unit 0. For each node visited, propagate the conversion factor to its children. For a child c with parent p and factor f, set baseUnitConversion[c] = (baseUnitConversion[p] * f) % MOD.
Continue traversing until all nodes have been visited.
Return the baseUnitConversion array.

Why it works: The algorithm works because the conversion relationships form a tree rooted at 0. Each node is visited exactly once, and its conversion factor is computed as the product of factors along the unique path from the root. Modulo arithmetic ensures values do not overflow.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def baseUnitConversions(self, conversions: List[List[int]]) -> List[int]:
        MOD = 10**9 + 7
        n = len(conversions) + 1
        tree = defaultdict(list)
        
        for u, v, f in conversions:
            tree[u].append((v, f))
        
        baseUnitConversion = [0] * n
        baseUnitConversion[0] = 1
        
        def dfs(node: int):
            for child, factor in tree[node]:
                baseUnitConversion[child] = (baseUnitConversion[node] * factor) % MOD
                dfs(child)
        
        dfs(0)
        return baseUnitConversion

Explanation: We first construct the tree from the conversion input. The dfs function recursively propagates conversion values from parent to child. Using modulo arithmetic avoids overflow. The final array contains the number of each unit equivalent to 1 unit of type 0.

Go Solution

package main

func baseUnitConversions(conversions [][]int) []int {
    const MOD int = 1e9 + 7
    n := len(conversions) + 1
    tree := make([][][2]int, n)
    
    for _, conv := range conversions {
        u, v, f := conv[0], conv[1], conv[2]
        tree[u] = append(tree[u], [2]int{v, f})
    }
    
    baseUnitConversion := make([]int, n)
    baseUnitConversion[0] = 1
    
    var dfs func(int)
    dfs = func(node int) {
        for _, child := range tree[node] {
            v, f := child[0], child[1]
            baseUnitConversion[v] = (baseUnitConversion[node] * f) % MOD
            dfs(v)
        }
    }
    
    dfs(0)
    return baseUnitConversion
}

Go-specific notes: The Go solution uses slices of slices for the adjacency list and arrays of length 2 to store child and factor. Modulo arithmetic is applied in the same way as Python.

Worked Examples

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

Node	Parent	Factor	baseUnitConversion
0	-	-	1
1	0	2	2
2	1	3	6

Result: [1, 2, 6]

Example 2: conversions = [[0,1,2],[0,2,3],[1,3,4],[1,4,5],[2,5,2],[4,6,3],[5,7,4]]

Node	Parent	Factor	baseUnitConversion
0	-	-	1
1	0	2	2
2	0	3	3
3	1	4	8
4	1	5	10
5	2	2	6
6	4	3	30
7	5	4	24

Result: [1, 2, 3, 8, 10, 6, 30, 24]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each node is visited once in DFS. Tree has n-1 edges.
Space	O(n)	Adjacency list and baseUnitConversion array both use O(n) space; recursion stack in DFS uses O(n) in worst case.

The time and space are both linear in n, which is optimal for this problem given the constraints.

Test Cases

# Basic examples
assert Solution().baseUnitConversions([[0,1,2],[1,2,3]]) == [1,2,6]  # Example 1
assert Solution().baseUnitConversions([[0,1,2],[0,2,3],[1,3,4],[1,4,5],[2,5,2],[4,6,3],[5,7,4]]) == [1,2,3,8,10,6,30,24]  # Example 2

# Minimum size
assert Solution().baseUnitConversions([[0,1,1]]) == [1,1]

# Large conversion factors
assert Solution().baseUnitConversions([[0,1,10**9],[1,2,10**9]]) == [1, 10**9 % (10**9 + 7), (10**9 * 10**9) % (10**9 + 7)]

# All factors 1
assert Solution().baseUnitConversions([[0,1,1],[1,2,1],[2,3,1]]) == [1,1,1,1]

Test	Why
Example 1	Simple tree of 3 nodes
Example 2	Larger tree, multiple branches
Minimum size	Edge case with smallest n
Large factors	Test modulo arithmetic
All factors 1	Checks propagation of factor 1

Edge Cases

Minimum input size (n=2): The algorithm handles this because the DFS simply propagates the single conversion from node 0 to 1.
**Large conversion factors The problem asks us to compute the conversion of every unit type into a "base" unit, specifically unit 0. We are given n types of units, numbered from 0 to n-1, and a list of conversions of length n-1. Each element in conversions is of the form [sourceUnit, targetUnit, conversionFactor], meaning one unit of sourceUnit equals conversionFactor units of targetUnit.

The goal is to return an array baseUnitConversion of length n, where each element represents how many units of that type are equivalent to a single unit of type 0, modulo $10^9 + 7$.

In simpler terms, the problem provides a tree-like structure of unit conversions rooted at unit 0. Starting from unit 0, we can propagate the conversions along the tree to compute the equivalent quantity of all units in terms of unit 0.

Constraints tell us that n can be as large as $10^5$, so any solution that scales worse than O(n) or O(n log n) may be too slow. It is guaranteed that the conversion graph forms a tree rooted at 0 (unique conversion path to each unit), which prevents cycles and simplifies computation.

Important edge cases include:

The minimum input size (n = 2), which tests if the algorithm handles very small trees.
Large conversion factors (up to $10^9$), which requires modulo arithmetic to avoid integer overflow.
Trees with varying depth, including very unbalanced trees.

Approaches

Brute Force Approach

A brute force approach would attempt to recursively compute the conversion from unit 0 to every other unit by searching through the conversions list for paths from 0 to the target. For each target unit, we would multiply the conversion factors along the path. This approach is correct but inefficient because for every unit we might scan the entire list, resulting in O(n²) time complexity.

Optimal Approach

The key observation is that the conversions form a tree rooted at 0. This means we can use Depth-First Search (DFS) or Breadth-First Search (BFS) to propagate conversions from unit 0 to all other units in a single traversal. We maintain an array baseUnitConversion where we store the cumulative conversion factor for each unit. For each edge [u, v, factor], if we know the conversion of u to unit 0, then the conversion of v is simply conversion[u] * factor. We also use modulo arithmetic to handle large numbers.

Using DFS or BFS, we can compute all conversions in O(n) time and O(n) space for the adjacency list and conversion array.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Search for paths individually for each unit
Optimal	O(n)	O(n)	Tree traversal using DFS/BFS propagating conversion factors

Algorithm Walkthrough

Initialize a list baseUnitConversion of length n with all elements set to 0. Set baseUnitConversion[0] = 1 since one unit of type 0 equals itself.
Construct an adjacency list graph from the conversions array. For each conversion [u, v, factor], store the edge from u to v with the factor.
Perform a DFS starting at node 0. For each visited node u, iterate through its neighbors (v, factor).
For each neighbor v, set baseUnitConversion[v] = (baseUnitConversion[u] * factor) % MOD, where MOD = 10^9 + 7.
Recursively call DFS on v to propagate conversions further down the tree.
Once DFS