Evaluate Division

Free with account Updated Nov 19, 2026 · 7 min read
On this page

    Problem statement

    You know some exchange rates and must answer conversion queries. Each rate (a, b, r) means one unit of currency a buys r units of b (r > 0), and all rates are consistent with each other. For each query (x, y), return how many units of y one unit of x buys, or -1.0 if it can't be worked out from the known rates. A currency that appears in no rate is unknown, even when the query is (x, x).

    This is LeetCode 399, Evaluate Division, where the rates are written as divisions a / b = r. Interviewers often ask it as currency conversion or unit conversion (meters, feet, inches), which is the same graph problem.

    Example

    Each known rate is an edge. GBP to JPY walks GBP → EUR → USD → JPY; going against an edge divides by its rate.
    Each known rate is an edge. GBP to JPY walks GBP → EUR → USD → JPY; going against an edge divides by its rate.
    rates:   USD -> EUR 0.8,   EUR -> GBP 0.5,   USD -> JPY 150
    queries: GBP -> JPY   ->  375.0      # 2 * 1.25 * 150
             EUR -> USD   ->  1.25       # 1 / 0.8
             USD -> GBP   ->  0.4        # 0.8 * 0.5
             USD -> CAD   -> -1.0        # CAD is unknown
             EUR -> EUR   ->  1.0
             CAD -> CAD   -> -1.0        # unknown, even to itself

    Constraints (assumed)

    • Up to 10⁴ rates and 10⁴ queries.
    • Currency names are strings; rates are positive floats.
    • The rates never contradict each other.

    What this question tests

    • Turning a word problem into a weighted graph, including the reverse edge.
    • A clean BFS or DFS that carries a running product.
    • Spotting that many queries on a fixed graph can share one precomputation.

    Questions to ask first

    1. Are the rates consistent? If two paths could give different answers, the problem changes. (Here: consistent.)
    2. What should a query on an unknown currency return? (Here: -1.0, even for (x, x).)
    3. How many queries compared with rates? Many queries favor precomputing.
    4. Can rates be zero or negative? (Here: no, so the reverse 1 / r is always defined.)