Is Unit Conversion II easy or hard?

Unit Conversion II is generally considered a medium difficulty problem. The challenge lies in recognizing that unit relationships form a graph and that conversions correspond to path multiplication. Once modeled correctly, the DFS or BFS traversal becomes straightforward.

Unit Conversion II Python/Java solution

Python and Java implementations typically build a HashMap or dictionary mapping each unit to a list of neighbors and conversion weights. A DFS or BFS traversal multiplies weights along the path until the target unit is found. Both languages achieve O(V + E) traversal time using standard graph structures.

How to solve Unit Conversion II in O(V + E)?

Construct a weighted adjacency list where each conversion adds two edges with reciprocal weights. Run DFS or BFS from the source unit, multiplying the weights along the path. Stop when the destination unit is reached. The traversal touches each node and edge at most once, giving O(V + E) complexity.

What is the best approach for Unit Conversion II?

The most common approach models the units as a weighted graph and uses DFS or BFS to evaluate conversion paths. Each edge stores a multiplier between two units. Traversing the graph while multiplying edge weights yields the final conversion value. This approach runs in O(V + E) time per query.

Is Unit Conversion II asked at Google/Amazon/Meta?

Graph traversal problems that evaluate relationships between entities are common in interviews at companies like Google, Amazon, and Meta. Variants involving equation evaluation, currency exchange, or unit conversion frequently appear. The key skill tested is modeling relationships as a weighted graph.

What data structure is used in Unit Conversion II?

The primary data structure is an adjacency list representing a weighted graph. Each node stores neighboring units and their conversion multipliers. DFS uses recursion or a stack, while BFS uses a queue to explore neighbors level by level.

What is the time complexity of Unit Conversion II?

Building the adjacency list takes O(E) time where E is the number of conversions. Each DFS or BFS traversal takes O(V + E) in the worst case because every node and edge may be explored. If conversions are precomputed per connected component, queries can be answered in O(1) time after O(V + E) preprocessing.

Description Hints 2 Solution Video 12:41

3535. Unit Conversion II

Medium61.5% acceptance1 companyPremium elsewhere, free here

There are n types of units indexed from 0 to n - 1.

You are given a 2D integer array conversions of length n - 1, where conversions[i] = [sourceUnit_i, targetUnit_i, conversionFactor_i]. This indicates that a single unit of type sourceUnit_i is equivalent to conversionFactor_i units of type targetUnit_i.

You are also given a 2D integer array queries of length q, where queries[i] = [unitA_i, unitB_i].

Return an array answer of length q where answer[i] is the number of units of type unitB_i equivalent to 1 unit of type unitA_i, and can be represented as p/q where p and q are coprime. Return each answer[i] as pq^-1 modulo 10⁹ + 7, where q^-1 represents the multiplicative inverse of q modulo 10⁹ + 7.

Example 1:

Input: conversions = [[0,1,2],[0,2,6]], queries = [[1,2],[1,0]]

Output: [3,500000004]

Explanation:

In the first query, we can convert unit 1 into 3 units of type 2 using the inverse of conversions[0], then conversions[1].
In the second query, we can convert unit 1 into 1/2 units of type 0 using the inverse of conversions[0]. We return 500000004 since it is the multiplicative inverse of 2.

Example 2:

Input: conversions = [[0,1,2],[0,2,6],[0,3,8],[2,4,2],[2,5,4],[3,6,3]], queries = [[1,2],[0,4],[6,5],[4,6],[6,1]]

Output: [3,12,1,2,83333334]

Explanation:

In the first query, we can convert unit 1 into 3 units of type 2 using the inverse of conversions[0], then conversions[1].
In the second query, we can convert unit 0 into 12 units of type 4 using conversions[1], then conversions[3].
In the third query, we can convert unit 6 into 1 unit of type 5 using the inverse of conversions[5], the inverse of conversions[2], conversions[1], then conversions[4].
In the fourth query, we can convert unit 4 into 2 units of type 6 using the inverse of conversions[3], the inverse of conversions[1], conversions[2], then conversions[5].
In the fifth query, we can convert unit 6 into 1/12 units of type 1 using the inverse of conversions[5], the inverse of conversions[2], then conversions[0]. We return 83333334 since it is the multiplicative inverse of 12.

Constraints:

2 <= n <= 10⁵
conversions.length == n - 1
0 <= sourceUnit_i, targetUnit_i < n
1 <= conversionFactor_i <= 10⁹
1 <= q <= 10⁵
queries.length == q
0 <= unitA_i, unitB_i < n
It is guaranteed that unit 0 can be uniquely converted into any other unit through a combination of forward or backward conversions.

Asked at 1 company

Tiktok

Topics

Hints open one at a time

Hint 1

Using a dfs, compute an array fromRoot such that fromRoot[a] is the number of units of type a equivalent to a single unit of type 0.

Hint 2

answer[i] = fromRoot[unitA_i]^-1 * fromRoot[unitB_i]

12:41

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[[0,1,2],[0,2,6]]
[[1,2],[1,0]]

Input

[[0,1,2],[0,2,6],[0,3,8],[2,4,2],[2,5,4],[3,6,3]]
[[1,2],[0,4],[6,5],[4,6],[6,1]]

Your code is saved on this device.Solution