Unit conversion i

Depth-First Search Breadth-First Search Graph Theory

54.3% acceptance

Feb 25, 2026

There are n types of units indexed from 0 to n-1. conversions[i] = [sourceUnit, targetUnit, conversionFactor]. Return baseUnitConversion[i] = units of type i equivalent to 1 unit of type 0, mod 10^9+7.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn base_unit_conversions(conversions: Vec<Vec<i32>>) -> Vec<i32> {
    const MOD: i64 = 1_000_000_007;
    let n = conversions.len() + 1;
    let mut adj: Vec<Vec<(usize, i64)>> = vec![vec![]; n];
    for c in &conversions {
      let (s, t, f) = (c[0] as usize, c[1] as usize, c[2] as i64);
      adj[s].push((t, f));
      adj[t].push((s, f));
    }

    let mut result = vec![0i64; n];
    result[0] = 1;
    let mut visited = vec![false; n];
    visited[0] = true;

    // BFS from node 0
    let mut queue = std::collections::VecDeque::new();
    queue.push_back(0usize);
    while let Some(u) = queue.pop_front() {
      for &(v, f) in &adj[u] {
        if !visited[v] {
          visited[v] = true;
          result[v] = result[u] * f % MOD;
          queue.push_back(v);
        }
      }
    }

    result.iter().map(|&x| x as i32).collect()
  }
}