Unit Conversion I - Video Solutions

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.