3528. Unit Conversion I

MediumDepth-First SearchBreadth-First SearchGraph

Problem Description

You have n types of units, numbered from 0 to n - 1. These units can be converted into one another based on specific rules given by a 2D integer array conversions, which has n - 1 entries. Each entry conversions[i] = [sourceUnit_i, targetUnit_i, conversionFactor_i] indicates that one unit of sourceUnit_i can be converted into conversionFactor_i units of targetUnit_i.

The task is to compute an array baseUnitConversion of length n. This array quantifies how many units of each type are equivalent to a single unit of type 0. Due to potentially large numbers, each baseUnitConversion[i] should be returned modulo 10^9 + 7.

Intuition

The problem can be visualized as a tree-like conversion structure, where unit 0 is the root and all other units are connected through conversion paths defined by the conversions array. Since there are n - 1 conversion paths for n units, the relationship can be uniquely traversed from unit 0 to any other unit.

We use Depth-First Search (DFS) to navigate this structure. Starting from unit 0, each conversion link in the path can be regarded as an edge leading to another unit with a specific conversion factor. We utilize an adjacency list to represent these relationships, which helps efficiently traverse from any given unit to units it can convert into, along with the associated conversion factors.

One begins DFS from the root 0, with an initial multiplication factor of 1, as unit 0 is equivalent to itself. As the DFS progresses, the function updates the equivalent conversion factors in the baseUnitConversion array. Precisely, when moving from unit s to unit t with conversion factor w, the product of the current multiplier and w (modulo 10^9 + 7) is passed to subsequent recursive calls. This effectively calculates how many units of each type are equivalent to one unit of type 0, concluding with the return of the assembled result.

Learn more about Depth-First Search, Breadth-First Search and Graph patterns.

Solution Approach

The solution employs a Depth-First Search (DFS) strategy to traverse the conversion tree starting from unit 0. This method leverages recursive traversal to compute the conversion factors for all units relative to unit 0.

Here's a step-by-step breakdown of the implementation:

Initialization:
- Define a constant mod as 10^9 + 7 to ensure that large numbers remain manageable through modulo operations.
- Determine n, the total number of units, which is one more than the length of the conversions array (n = len(conversions) + 1).
Graph Representation:
- Construct an adjacency list g of size n to represent conversion relationships. Each entry g[i] will store tuples (t, w), where t is the target unit and w is the conversion factor from unit i to unit t.
Populating the Graph:
- Iterate over each conversion in conversions. For each conversion [s, t, w], add (t, w) to g[s], establishing a directed edge representing the conversion from s to t with factor w.
Depth-First Search (DFS) Function:
- Implement a recursive DFS function dfs(s: int, mul: int) -> None:
  - s is the current unit being processed.
  - mul is the conversion multiplier from unit 0 to unit s.
  - Assign mul to ans[s], indicating the equivalent conversion factor for unit s.
  - For each adjacent unit t connected to s through g[s], recursively call dfs(t, mul * w % mod), updating the multiplier based on the conversion factor w.
Solution Execution:
- Initialize the ans array with zeros, designed to store conversion factors for all units.
- Invoke dfs(0, 1) to start traversal from unit 0 with a multiplier of 1.
Result:
- Upon completion of the DFS traversal, ans contains the conversion factors for each unit in terms of unit 0, modulated by mod.

This algorithm efficiently computes the required conversion factors by exploring each conversion path using DFS, ensuring clarity and accuracy in determining how units relate to the base unit 0.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example with n = 3 units and conversions defined as follows:

conversions = [[0, 1, 2], [1, 2, 3]]

These indicate that:

One unit of type 0 converts to 2 units of type 1.
One unit of type 1 converts to 3 units of type 2.

We'll use these conversions to compute the baseUnitConversion array, which represents how many units of each type are equivalent to one unit of type 0, using the DFS approach described in the solution.

Step-by-Step Execution:

Initialization:
- Set the mod constant to 10^9 + 7.
- Calculate n = len(conversions) + 1 = 3.
Graph Representation:
- Create an adjacency list g with n empty lists: g = [[], [], []].
Populating the Graph:
- For the conversion [0, 1, 2], add (1, 2) to g[0]: g = [[(1, 2)], [], []].
- For the conversion [1, 2, 3], add (2, 3) to g[1]: g = [[(1, 2)], [(2, 3)], []].
Depth-First Search (DFS) Function:
- Define a recursive DFS function. Initialize ans = [0, 0, 0].
- Start DFS with dfs(0, 1):
  - Set ans[0] = 1.
  - Process g[0] = [(1, 2)]: for (1, 2), call dfs(1, 1 * 2 % mod):
    - Set ans[1] = 2 (conversion factor from unit 0 to unit 1 is 2).
    - Process g[1] = [(2, 3)]: for (2, 3), call dfs(2, 2 * 3 % mod):
      - Set ans[2] = 6 (conversion factor from unit 0 to unit 2 is 6).
Result:
- The ans array is [1, 2, 6].
- This means:
  - 1 unit of type 0 is equivalent to 1 unit of type 0.
  - 2 units of type 1 are equivalent to 1 unit of type 0.
  - 6 units of type 2 are equivalent to 1 unit of type 0.

This walkthrough illustrates how DFS recursively calculates each unit's conversion factor relative to unit 0, providing the complete baseUnitConversion array.

Solution Implementation

1from typing import List
2
3class Solution:
4    def baseUnitConversions(self, conversions: List[List[int]]) -> List[int]:
5        # Perform Depth-First Search to compute conversion multipliers
6        def dfs(source: int, multiplier: int) -> None:
7            # Store the computed multiplier for the current unit
8            result[source] = multiplier
9            # Traverse each connected unit from the current unit
10            for target, weight in graph[source]:
11                # Calculate the new multiplier and perform DFS recursively
12                dfs(target, (multiplier * weight) % MOD)
13
14        MOD = 10**9 + 7  # Modulo value for large number handling
15        n = len(conversions) + 1  # Total number of base units
16        graph = [[] for _ in range(n)]  # Graph representation for units and their conversion rates
17
18        # Build the graph based on conversions
19        for source, target, weight in conversions:
20            graph[source].append((target, weight))
21
22        result = [0] * n  # Array to store conversion multipliers for each unit
23        dfs(0, 1)  # Start DFS from base unit 0 with initial multiplier 1
24      
25        return result
26

1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4
5class Solution {
6    // Constant to define the modulo value for calculations
7    private final int MOD = (int) 1e9 + 7;
8  
9    // Adjacency list to represent the graph of conversions
10    private List<int[]>[] graph;
11  
12    // Array to store the conversion results
13    private int[] result;
14  
15    // Variable to store the number of nodes (units)
16    private int numUnits;
17
18    // Method to compute base unit conversions given the conversion relationships
19    public int[] baseUnitConversions(int[][] conversions) {
20        // Initialize the number of units to the number of conversions plus one
21        numUnits = conversions.length + 1;
22
23        // Initialize the graph to hold the list of conversions for each unit
24        graph = new List[numUnits];
25        Arrays.setAll(graph, k -> new ArrayList<>());
26
27        // Initialize the result array to store final conversion values
28        result = new int[numUnits];
29      
30        // Populate the graph with conversion information between units
31        for (int[] conversion : conversions) {
32            // Each conversion is represented as [fromUnit, toUnit, conversionFactor]
33            graph[conversion[0]].add(new int[] {conversion[1], conversion[2]});
34        }
35
36        // Start the depth-first search from the base unit (0) with an initial multiplier of 1
37        dfs(0, 1);
38      
39        // Return the array containing all conversion results
40        return result;
41    }
42
43    // Recursive Depth First Search (DFS) to traverse the graph and calculate conversion factors
44    private void dfs(int source, long multiplier) {
45        // Set the conversion result for the current unit
46        result[source] = (int) multiplier;
47      
48        // Traverse all adjacent units from the current unit
49        for (int[] edge : graph[source]) {
50            // Perform DFS on the adjacent unit, updating the conversion factor
51            dfs(edge[0], multiplier * edge[1] % MOD);
52        }
53    }
54}
55

1#include <vector>
2#include <utility>
3
4class Solution {
5public:
6    // This method performs a depth-first search to calculate and return the
7    // conversion values of base units given a list of conversion rules.
8    std::vector<int> baseUnitConversions(std::vector<std::vector<int>>& conversions) {
9        const int mod = 1e9 + 7; // Define a constant for modulo operations.
10        int n = conversions.size() + 1; // Determine the number of nodes (units).
11      
12        // Create an adjacency list for the conversion graph.
13        std::vector<std::vector<std::pair<int, int>>> graph(n);
14      
15        // Initialize the result vector with size n to hold conversion values.
16        std::vector<int> results(n);
17      
18        // Populate the adjacency list with conversion pairs and weights.
19        for (const auto& conversion : conversions) {
20            graph[conversion[0]].push_back({conversion[1], conversion[2]});
21        }
22      
23        // Lambda function for depth-first search with self-reference to traverse the graph.
24        auto dfs = [&](auto&& dfs, int source, long long accumulated_value) -> void {
25            results[source] = accumulated_value; // Set the conversion value for the current node.
26            for (auto [target, weight] : graph[source]) {
27                // Recursively apply DFS to adjacent nodes with updated conversion values.
28                dfs(dfs, target, accumulated_value * weight % mod);
29            }
30        };
31      
32        dfs(dfs, 0, 1); // Start DFS from the root node (index 0) with initial conversion value of 1.
33        return results; // Return the result vector containing conversion values for all units.
34    }
35};
36

1// Defines the conversion function for base units.
2function baseUnitConversions(conversions: number[][]): number[] {
3    // Define the modulo value for large number computations.
4    const mod = BigInt(1e9 + 7);
5  
6    // Calculate the size of the graph based on the number of conversions.
7    const n = conversions.length + 1;
8  
9    // Initialize the graph as an adjacency list.
10    const graph: { to: number; weight: number }[][] = Array.from({ length: n }, () => []);
11  
12    // Populate the graph with the conversions data.
13    for (const [source, target, weight] of conversions) {
14        graph[source].push({ to: target, weight });
15    }
16  
17    // Initialize the answers array to store conversion results for each base unit.
18    const results: number[] = Array(n).fill(0);
19  
20    // Depth-first search function for traversing the graph.
21    const dfs = (currentNode: number, currentMultiplier: number) => {
22        // Set the current node's conversion result.
23        results[currentNode] = currentMultiplier;
24      
25        // Traverse the adjacency list for the current node.
26        for (const { to, weight } of graph[currentNode]) {
27            // Calculate new multiplier and continue DFS on the child node.
28            dfs(to, Number((BigInt(currentMultiplier) * BigInt(weight)) % mod));
29        }
30    };
31  
32    // Begin DFS from the root node with an initial multiplier of 1.
33    dfs(0, 1);
34  
35    // Return the array of conversion results.
36    return results;
37}
38

Time and Space Complexity

The time complexity of the code is O(n), where n is the number of units. This is because the DFS traversal visits each node exactly once, and there are n nodes corresponding to n units.

The space complexity of the code is also O(n), where n is the number of units. This is due to the space needed to store the adjacency list g and the ans list, both of which have size proportional to the number of units n.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Linear Search

Binary Search

Quick Select

Hash Set

I don't know