Skip to main content
Talentd

Unit Conversion II - Solution & Explanation

MediumPremiumFree on FleetCodeArrayMathDepth-First SearchBreadth-First Search11 min readAsked at: Tiktok
Practice this problem

Problem Statement

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] = [sourceUniti, targetUniti, conversionFactori]. This indicates that a single unit of type sourceUniti is equivalent to conversionFactori units of type targetUniti.

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

Return an array answer of length q where answer[i] is the number of units of type unitBi equivalent to 1 unit of type unitAi, and can be represented as p/q where p and q are coprime. Return each answer[i] as pq-1 modulo 109 + 7, where q-1 represents the multiplicative inverse of q modulo 109 + 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 <= 105
  • conversions.length == n - 1
  • 0 <= sourceUniti, targetUniti < n
  • 1 <= conversionFactori <= 109
  • 1 <= q <= 105
  • queries.length == q
  • 0 <= unitAi, unitBi < n
  • It is guaranteed that unit 0 can be uniquely converted into any other unit through a combination of forward or backward conversions.

Approach Overview

Problem Overview: You are given relationships that define how one unit converts to another. Each conversion acts like an edge with a multiplier. The task is to determine the correct conversion value between units by chaining these relationships together.

Approach 1: Graph Modeling + DFS Traversal (O(V + E) per query time, O(V + E) space)

Treat each unit as a node in a weighted graph. A conversion like a → b = k becomes two edges: a → b (k) and b → a (1/k). To compute a requested conversion, run a depth-first search from the source unit and multiply weights along the path until the destination is reached. This works because any valid conversion chain forms a path in the graph. DFS is simple to implement with recursion and performs well for sparse graphs.

Approach 2: Breadth-First Search Path Evaluation (O(V + E) per query time, O(V + E) space)

The graph construction remains the same, but traversal uses a queue instead of recursion. Starting from the source unit, push neighbors into a queue while tracking the cumulative conversion multiplier. The first time you reach the target unit, the accumulated product gives the result. Breadth-first search is often preferred when you want predictable iteration without recursion depth concerns. The algorithm scans neighbors level by level until the conversion path is found.

Approach 3: Component Precomputation with DFS (O(V + E) preprocessing, O(1) queries, O(V + E) space)

If many conversions must be answered, precompute relative values for every node within a connected component. Pick an arbitrary root unit and run DFS to assign each unit a value relative to that root. Once stored, any conversion between two units in the same component is simply the ratio of their stored values. This converts repeated graph traversals into constant-time lookups after a single traversal.

Recommended for interviews: The adjacency list graph with DFS is the expected solution. It demonstrates correct modeling of multiplicative relationships and efficient traversal using graph techniques. Candidates often start with DFS, then discuss BFS as an alternative using breadth-first search or depth-first search. The key insight is recognizing that unit relationships form a weighted graph where conversions correspond to path multiplication.

Solution

The conversion relations form a directed tree rooted at 0. Starting a DFS from node 0, we maintain res[i] as the number of units of type i that equal 1 unit of type 0.

For a query (unitA, unitB), the answer is \frac{res[unitB]}{res[unitA]}, which modulo 10^9 + 7 equals res[unitB] * res[unitA]^(MOD - 2) % MOD, where MOD - 2 is used to compute the modular inverse via Fermat's little theorem.

The time complexity is O(n + q log MOD) and the space complexity is O(n), where n is the number of unit types and q is the number of queries.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Graph + DFS traversalO(V + E) per queryO(V + E)General solution when queries are limited and recursion is acceptable
Graph + BFS traversalO(V + E) per queryO(V + E)Preferred when avoiding recursion depth or when using iterative traversal
Component precomputationO(V + E) preprocessing, O(1) per queryO(V + E)Best when the graph is static and many conversion queries must be answered quickly

Video Solution

leetcode 3535 Unit Conversion II | dfs or bfs, mod multiplicative inverse • Code-Yao • 233 views views

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Unit Conversion II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays