Skip to main content
Talentd

Unit Conversion I - Solution & Explanation

MediumDepth-First SearchBreadth-First SearchGraph11 min readAsked at: Adobe
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.

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:

  • Convert a single unit of type 0 into 2 units of type 1 using conversions[0].
  • Convert a single unit of type 0 into 6 units of type 2 using 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:

  • Convert a single unit of type 0 into 2 units of type 1 using conversions[0].
  • Convert a single unit of type 0 into 3 units of type 2 using conversions[1].
  • Convert a single unit of type 0 into 8 units of type 3 using conversions[0], then conversions[2].
  • Convert a single unit of type 0 into 10 units of type 4 using conversions[0], then conversions[3].
  • Convert a single unit of type 0 into 6 units of type 5 using conversions[1], then conversions[4].
  • Convert a single unit of type 0 into 30 units of type 6 using conversions[0], conversions[3], then conversions[5].
  • Convert a single unit of type 0 into 24 units of type 7 using conversions[1], conversions[4], then conversions[6].

 

Constraints:

  • 2 <= n <= 105
  • conversions.length == n - 1
  • 0 <= sourceUniti, targetUniti < n
  • 1 <= conversionFactori <= 109
  • It is guaranteed that unit 0 can be converted into any other unit through a unique combination of conversions without using any conversions in the opposite direction.

Approach Overview

Problem Overview: You are given relationships between different measurement units (for example, 1 meter = 100 centimeter). The task is to determine conversion values between units that may not be directly connected. Think of each unit as a node and each conversion as a weighted edge that represents the multiplication factor between them.

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

Model the problem as a weighted graph. Each unit becomes a node, and each conversion rule adds two directed edges: A -> B with weight w and B -> A with weight 1/w. When you need to compute a conversion between two units, run a depth-first search starting from the source unit and multiply edge weights along the path. A visited set prevents cycles. The key insight is that chained conversions correspond to multiplying weights along a path in the graph. DFS works well because you only need one valid path to compute the result.

This approach naturally fits problems involving graph traversal. The adjacency list stores neighbors and weights, and recursion explores reachable units until the destination is found. Each query explores at most all vertices and edges in the connected component.

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

The same graph structure can be traversed using a queue instead of recursion. Start from the source unit with an accumulated conversion factor of 1. For each neighbor, multiply the current factor by the edge weight and push the result into the queue. Once the target unit is reached, the accumulated product gives the conversion value. BFS guarantees the shortest number of edges explored first, though for multiplicative conversions any valid path works.

BFS is often preferred when recursion depth may become large or when you want an iterative solution. It still uses an adjacency list and a visited set, making it a standard application of breadth-first search and depth-first search patterns on graphs.

Recommended for interviews: The DFS graph approach is typically expected. Start by explaining the graph modeling step—units as nodes and conversion ratios as weighted edges. Show that multiplying weights along a path produces the correct conversion. BFS is an equally valid alternative, but DFS usually leads to a simpler implementation. Demonstrating both shows strong understanding of graph traversal techniques.

Solution

Since the problem guarantees that unit 0 can be converted to any other unit through a unique conversion path, we can use Depth-First Search (DFS) to traverse all unit conversion relationships. Additionally, since the length of the conversions array is n - 1, representing n - 1 conversion relationships, we can treat the unit conversion relationships as a tree, where the root node is unit 0, and the other nodes are the other units.

We can use an adjacency list g to represent the unit conversion relationships, where g[i] represents the units that unit i can convert to and the corresponding conversion factors.

Then, we start the DFS from the root node 0, i.e., call the function dfs(s, mul), where s represents the current unit, and mul represents the conversion factor from unit 0 to unit s. Initially, s = 0, mul = 1. In each recursion, we store the conversion factor mul of the current unit s into the answer array, then traverse all adjacent units t of the current unit s, and recursively call dfs(t, mul times w \mod (10^9 + 7)), where w is the conversion factor from unit s to unit t.

Finally, we return the answer array.

The complexity is O(n), and the space complexity is O(n), where n is the number of units.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
DFS Graph TraversalO(V + E) per queryO(V + E)Standard solution for weighted conversion graphs
BFS Graph TraversalO(V + E) per queryO(V + E)Iterative traversal when avoiding recursion depth issues

Video Solution

3528. Unit Conversion I (Leetcode Medium) • Programming Live with Larry • 342 views views

Watch 1 more video solutions →

Frequently Asked Questions

Is Unit Conversion I easy or hard?
Unit Conversion I is generally classified as a medium difficulty problem. The challenge lies in recognizing that the relationships form a weighted graph and that conversions correspond to multiplying weights along traversal paths. Once the graph model is clear, the DFS or BFS implementation is straightforward.
Unit Conversion I Python/Java solution
Python and Java implementations typically store the graph in a hash map where each unit maps to a list of neighbors with weights. DFS is implemented either recursively or using an explicit stack. During traversal, multiply edge weights to maintain the current conversion value until the target unit is reached.
How to solve Unit Conversion I in O(V + E)?
Build an adjacency list where each unit points to neighbors with conversion weights. For a query from unit A to unit B, run DFS or BFS starting at A while tracking the accumulated product of weights. Once B is reached, return the accumulated value. The traversal touches each node and edge at most once, resulting in O(V + E) complexity.
What is the best approach for Unit Conversion I?
The most common solution models the conversions as a weighted graph and uses depth-first search (DFS) to compute ratios between units. Each unit is a node and each conversion is an edge with a multiplicative weight. Traversing a path from source to target multiplies edge weights to produce the final conversion. This runs in O(V + E) time per query.
Is Unit Conversion I asked at Google/Amazon/Meta?
Graph traversal and ratio evaluation problems frequently appear in interviews at companies like Google, Amazon, and Meta. While the exact problem title may vary, the pattern of modeling relationships as a graph and computing values through DFS or BFS is a common interview topic.
What data structure is used in Unit Conversion I?
The primary data structure is a weighted adjacency list representing a graph. Each node stores neighboring units along with their conversion factors. A visited set or hash set is used during traversal to avoid revisiting nodes and forming cycles.
What is the time complexity of Unit Conversion I?
The graph construction step takes O(E) time where E is the number of conversion relationships. Each query uses DFS or BFS traversal and in the worst case explores all vertices and edges in the connected component, giving O(V + E) time per query and O(V + E) space for the adjacency list.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Binary Tree Inorder Traversal

Next

Validate Binary Search Tree