Unit Conversion II solution and explanation
The problem
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], thenconversions[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], thenconversions[1]. - In the second query, we can convert unit 0 into 12 units of type 4 using
conversions[1], thenconversions[3]. - In the third query, we can convert unit 6 into 1 unit of type 5 using the inverse of
conversions[5], the inverse ofconversions[2],conversions[1], thenconversions[4]. - In the fourth query, we can convert unit 4 into 2 units of type 6 using the inverse of
conversions[3], the inverse ofconversions[1],conversions[2], thenconversions[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 ofconversions[2], thenconversions[0]. We return 83333334 since it is the multiplicative inverse of 12.
Constraints:
2 <= n <= 105conversions.length == n - 10 <= sourceUniti, targetUniti < n1 <= conversionFactori <= 1091 <= q <= 105queries.length == q0 <= 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.
class Solution:
def queryConversions(
self, conversions: List[List[int]], queries: List[List[int]]
) -> List[int]:
def dfs(s: int, mul: int) -> None:
res[s] = mul
for t, w in g[s]:
dfs(t, mul * w % mod)
mod = 10**9 + 7
n = len(conversions) + 1
g = [[] for _ in range(n)]
for s, t, w in conversions:
g[s].append((t, w))
res = [0] * n
dfs(0, 1)
ans = []
for x, y in queries:
ans.append(res[y] * pow(res[x], mod - 2, mod) % mod)
return ansclass Solution {
private final int mod = (int) 1e9 + 7;
private List<int[]>[] g;
private int[] res;
public int[] queryConversions(int[][] conversions, int[][] queries) {
int n = conversions.length + 1;
g = new List[n];
Arrays.setAll(g, k -> new ArrayList<>());
for (var e : conversions) {
g[e[0]].add(new int[] {e[1], e[2]});
}
res = new int[n];
dfs(0, 1);
int[] ans = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
int x = queries[i][0], y = queries[i][1];
ans[i] = (int) ((long) res[y] * qpow(res[x], mod - 2) % mod);
}
return ans;
}
private void dfs(int s, long mul) {
res[s] = (int) mul;
for (var e : g[s]) {
dfs(e[0], mul * e[1] % mod);
}
}
private long qpow(long x, int n) {
long res = 1;
while (n > 0) {
if ((n & 1) == 1) {
res = res * x % mod;
}
x = x * x % mod;
n >>= 1;
}
return res;
}
}class Solution {
public:
vector<int> queryConversions(vector<vector<int>>& conversions, vector<vector<int>>& queries) {
const int mod = 1e9 + 7;
int n = conversions.size() + 1;
vector<vector<pair<int, int>>> g(n);
for (auto& e : conversions) {
g[e[0]].emplace_back(e[1], e[2]);
}
vector<int> res(n);
auto dfs = [&](this auto&& dfs, int s, long long mul) -> void {
res[s] = mul;
for (auto [t, w] : g[s]) {
dfs(t, mul * w % mod);
}
};
dfs(0, 1);
auto qpow = [&](long long x, int n) {
long long res = 1;
while (n) {
if (n & 1) {
res = res * x % mod;
}
x = x * x % mod;
n >>= 1;
}
return res;
};
vector<int> ans;
for (auto& q : queries) {
ans.push_back(res[q[1]] * qpow(res[q[0]], mod - 2) % mod);
}
return ans;
}
};function queryConversions(conversions: number[][], queries: number[][]): number[] {
const mod = BigInt(1e9 + 7);
const n = conversions.length + 1;
const g: { t: number; w: number }[][] = Array.from({ length: n }, () => []);
for (const [s, t, w] of conversions) {
g[s].push({ t, w });
}
const res: number[] = Array(n).fill(0);
const dfs = (s: number, mul: number): void => {
res[s] = mul;
for (const { t, w } of g[s]) {
dfs(t, Number((BigInt(mul) * BigInt(w)) % mod));
}
};
dfs(0, 1);
const qpow = (x: number, n: number): number => {
let res = 1n;
let a = BigInt(x);
while (n > 0) {
if (n & 1) {
res = (res * a) % mod;
}
a = (a * a) % mod;
n >>= 1;
}
return Number(res);
};
const ans: number[] = [];
for (const [x, y] of queries) {
ans.push(Number((BigInt(res[y]) * BigInt(qpow(res[x], 1e9 + 5))) % mod));
}
return ans;
}func queryConversions(conversions [][]int, queries [][]int) []int {
const mod = int(1e9 + 7)
n := len(conversions) + 1
g := make([][]struct{ t, w int }, n)
for _, e := range conversions {
s, t, w := e[0], e[1], e[2]
g[s] = append(g[s], struct{ t, w int }{t, w})
}
res := make([]int, n)
var dfs func(int, int)
dfs = func(s, mul int) {
res[s] = mul
for _, e := range g[s] {
dfs(e.t, mul*e.w%mod)
}
}
dfs(0, 1)
qpow := func(x, n int) int {
res := 1
for n > 0 {
if n&1 > 0 {
res = res * x % mod
}
x = x * x % mod
n >>= 1
}
return res
}
ans := make([]int, len(queries))
for i, q := range queries {
ans[i] = res[q[1]] * qpow(res[q[0]], mod-2) % mod
}
return ans
}impl Solution {
pub fn query_conversions(conversions: Vec<Vec<i32>>, queries: Vec<Vec<i32>>) -> Vec<i32> {
const MOD: i64 = 1_000_000_007;
let n = conversions.len() + 1;
let mut g = vec![Vec::<(usize, i64)>::new(); n];
for e in conversions {
g[e[0] as usize].push((e[1] as usize, e[2] as i64));
}
let mut res = vec![0_i64; n];
fn dfs(s: usize, mul: i64, g: &Vec<Vec<(usize, i64)>>, res: &mut Vec<i64>) {
res[s] = mul;
for &(t, w) in &g[s] {
dfs(t, mul * w % MOD, g, res);
}
}
dfs(0, 1, &g, &mut res);
fn qpow(mut x: i64, mut n: i32) -> i64 {
let mut res = 1_i64;
while n > 0 {
if n & 1 == 1 {
res = res * x % MOD;
}
x = x * x % MOD;
n >>= 1;
}
res
}
let mut ans = Vec::with_capacity(queries.len());
for q in queries {
let x = q[0] as usize;
let y = q[1] as usize;
ans.push((res[y] * qpow(res[x], 1_000_000_005) % MOD) as i32);
}
ans
}
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Graph + DFS traversal | O(V + E) per query | O(V + E) | General solution when queries are limited and recursion is acceptable |
| Graph + BFS traversal | O(V + E) per query | O(V + E) | Preferred when avoiding recursion depth or when using iterative traversal |
| Component precomputation | O(V + E) preprocessing, O(1) per query | O(V + E) | Best when the graph is static and many conversion queries must be answered quickly |
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.