Problem Statement in English

You’re given a list of unit conversions, where each conversion is represented as a list of three integers [src, dst, cost], which means that cost units of src are equal to 1 unit of dst.

You need to find the conversion factor for each unit in the list, starting from the first unit (index 0).

Approach

All you really need, is to realize that this is a graph problem. After that it’s one straightforward DFS away.

Solution in Python


class Solution:
    def baseUnitConversions(self, conversions: List[List[int]]) -> List[int]:
        n = 1
        adjList = defaultdict(list)
        MOD = 10**9+7

        for src, dst, cost in conversions:
            adjList[src].append((dst, cost))
            if dst not in adjList:
                n+=1


        res = [1] * n

        def dfs(node, factor):
            for nei, cost in adjList[node]:
                new_cost = factor * cost
                res[nei] = new_cost % MOD
                dfs(nei, new_cost % MOD)

        dfs(0 ,1)

        return res

Complexity

  • Time: $O(n)$
    Where $n$ is the number of nodes in the graph. We are doing a DFS traversal of the graph, which takes linear time.

  • Space: $O(n)$
    Since we are storing the graph in an adjacency list, the space complexity is linear in the number of nodes.

And we are done.