3528.Unit Conversion I

Link: 3528. Unit Conversion I - Medium

Question

Restate the problem

Given list of list, conversions, length is n-1
Return an array, length is n
conversions[i] = [sourceUniti, targetUniti, conversionFactori]
$targetUniti=sourceUniti\ast conversionFactori$

res[v] = res[u] * factor[i] (% MOD)

---

Method 1: Brute Force, trace back, O($n^2$)

• Initial parent = [(-1, 1)] * n,
• Build parent[target] = (source, weight)
• Initial res = [0] * n, res[0] = 1
• Iterate range from 1 to n-1
  • cur = i
  • while cur != 0
    • par, weight = parent[cur]
    • val = val * weight
    • cur = parent
  • res[i] = val

Method2 - BFS

Approach

• Build an adjacency list graph[u] -> [(v, w)] where w means 1 unit of u = w units of v.
• Then run BFS from node 0. Let res[u] be “how many units of type u equal 1 unit of type 0”.
• When we traverse an edge u -> v with factor w, we can compute:
  • res[v] = res[u] * w (mod MOD)

Because the problem guarantees a unique path from 0 to every node, each node’s value is computed exactly once.

Complexity

• Time Complexity: O(n)
• Space Complexity: O(n)

Edge Case

• if no conversions: return []

Code

class Solution:
    def baseUnitConversions(self, conversions: List[List[int]]) -> List[int]:
        n = len(conversions) + 1
        
        MOD = 10 ** 9 + 7
        graph = defaultdict(list)
        for s, t, weight in conversions:
            graph[s].append((t, weight))
        
        res = [0] * n
        res[0] = 1
        visited = [False] * n
        visited[0] = True
 
        queue = deque()
        queue.append(0)
        while queue:
            s = queue.popleft()
            for t, w in graph[s]:
                if not visited[t]: # not visited
                    res[t] = res[s] * w % MOD
                    visited[t] = True
                    queue.append(t)
        
        return res

---

History

Jan-21-2026 Peeked,

• Struggled to understand what the question was asking
• Didn’t identify the correct DSA (graph/tree) at first
• Didn’t have a clear brute-force baseline, so I got stuck early