Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using core interview patterns strategy.
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.
Return an array baseUnitConversion of length n, where baseUnitConversion[i] is the number of units of type i equivalent to a single unit of type 0. Since the answer may be large, return each baseUnitConversion[i] modulo 109 + 7.
Example 1:
Input: conversions = [[0,1,2],[1,2,3]]
Output: [1,2,6]
Explanation:
conversions[0].conversions[0], then conversions[1].Example 2:
Input: conversions = [[0,1,2],[0,2,3],[1,3,4],[1,4,5],[2,5,2],[4,6,3],[5,7,4]]
Output: [1,2,3,8,10,6,30,24]
Explanation:
conversions[0].conversions[1].conversions[0], then conversions[2].conversions[0], then conversions[3].conversions[1], then conversions[4].conversions[0], conversions[3], then conversions[5].conversions[1], conversions[4], then conversions[6].Constraints:
2 <= n <= 105conversions.length == n - 10 <= sourceUniti, targetUniti < n1 <= conversionFactori <= 109Problem summary: 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. Return an array baseUnitConversion of length n, where baseUnitConversion[i] is the number of units of type i equivalent to a single unit of type 0. Since the answer may be large, return each baseUnitConversion[i] modulo 109 + 7.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: General problem-solving
[[0,1,2],[1,2,3]]
[[0,1,2],[0,2,3],[1,3,4],[1,4,5],[2,5,2],[4,6,3],[5,7,4]]
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3528: Unit Conversion I
class Solution {
private final int mod = (int) 1e9 + 7;
private List<int[]>[] g;
private int[] ans;
private int n;
public int[] baseUnitConversions(int[][] conversions) {
n = conversions.length + 1;
g = new List[n];
Arrays.setAll(g, k -> new ArrayList<>());
ans = new int[n];
for (var e : conversions) {
g[e[0]].add(new int[] {e[1], e[2]});
}
dfs(0, 1);
return ans;
}
private void dfs(int s, long mul) {
ans[s] = (int) mul;
for (var e : g[s]) {
dfs(e[0], mul * e[1] % mod);
}
}
}
// Accepted solution for LeetCode #3528: Unit Conversion I
func baseUnitConversions(conversions [][]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})
}
ans := make([]int, n)
var dfs func(s int, mul int)
dfs = func(s int, mul int) {
ans[s] = mul
for _, e := range g[s] {
dfs(e.t, mul*e.w%mod)
}
}
dfs(0, 1)
return ans
}
# Accepted solution for LeetCode #3528: Unit Conversion I
class Solution:
def baseUnitConversions(self, conversions: List[List[int]]) -> List[int]:
def dfs(s: int, mul: int) -> None:
ans[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))
ans = [0] * n
dfs(0, 1)
return ans
// Accepted solution for LeetCode #3528: Unit Conversion I
// Rust example auto-generated from java reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
pub fn rust_example() {
// Port the logic from the reference block below.
}
}
// Reference (java):
// // Accepted solution for LeetCode #3528: Unit Conversion I
// class Solution {
// private final int mod = (int) 1e9 + 7;
// private List<int[]>[] g;
// private int[] ans;
// private int n;
//
// public int[] baseUnitConversions(int[][] conversions) {
// n = conversions.length + 1;
// g = new List[n];
// Arrays.setAll(g, k -> new ArrayList<>());
// ans = new int[n];
// for (var e : conversions) {
// g[e[0]].add(new int[] {e[1], e[2]});
// }
// dfs(0, 1);
// return ans;
// }
//
// private void dfs(int s, long mul) {
// ans[s] = (int) mul;
// for (var e : g[s]) {
// dfs(e[0], mul * e[1] % mod);
// }
// }
// }
// Accepted solution for LeetCode #3528: Unit Conversion I
function baseUnitConversions(conversions: 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 ans: number[] = Array(n).fill(0);
const dfs = (s: number, mul: number) => {
ans[s] = mul;
for (const { t, w } of g[s]) {
dfs(t, Number((BigInt(mul) * BigInt(w)) % mod));
}
};
dfs(0, 1);
return ans;
}
Use this to step through a reusable interview workflow for this problem.
Two nested loops check every pair or subarray. The outer loop fixes a starting point, the inner loop extends or searches. For n elements this gives up to n²/2 operations. No extra space, but the quadratic time is prohibitive for large inputs.
Most array problems have an O(n²) brute force (nested loops) and an O(n) optimal (single pass with clever state tracking). The key is identifying what information to maintain as you scan: a running max, a prefix sum, a hash map of seen values, or two pointers.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.