Medium

Unit Conversion I

LAB

Given directed conversions [from,to,factor], return the product to convert from source to target, or -1 if unreachable.

EXAMPLES

Example 1

Input
{
  "conversions": [
    [
      0,
      1,
      12
    ],
    [
      1,
      2,
      3
    ]
  ],
  "source": 0,
  "target": 2
}

Output
36

FUNCTION SHAPE

conversions: intMatrixsource: inttarget: int→int

SOLUTION NOTE

Tree DP from root. Multiply conversion factors along path from unit 0 to each unit.

Reveal reference solution +

pythonREFERENCE

def baseUnitConversions(self, conversions: List[List[int]]) -> List[int]:
    n = len(conversions)
    MOD = 10**9 + 7
    parent = {}
    for u, v, w in conversions:
        parent[v] = (u, w)

    @cache
    def dp(i):
        if i == 0: return 1
        par, w = parent[i]
        return (w * dp(par)) % MOD

    return [dp(i) for i in range(n + 1)]

TimeO(n)

SpaceO(n)

Open on LeetCode ↗