Best Currency Conversion
MediumGraph · Coinbase
An exchange publishes one-way quotes. Each quote [from_currency, to_currency, rate] means one unit of from_currency can be converted into rate units of to_currency. A quote can only be used in the direction it is listed; the reverse conversion exists only if it is quoted separately. The same pair may be quoted more than once.
You may chain any number of conversions. Return the maximum amount of target you can end up with, starting from exactly one unit of source.
- If
source == target, return1.0. - If
targetcannot be reached fromsource, return-1.0.
The market has no arbitrage: for any sequence of conversions that starts and ends in the same currency, the product of the rates is less than 1. (So repeating a loop never helps, and a best answer always exists.) Answers are compared with an absolute tolerance of 10^-6.
Example 1
- Input:
- rates = [["USD", "EUR", 0.9], ["EUR", "GBP", 0.85], ["USD", "GBP", 0.75], ["GBP", "JPY", 180.0], ["EUR", "JPY", 150.0]], source = "USD", target = "JPY"
- Output:
- 137.7
- Explanation
- Going USD -> GBP -> JPY gives 0.75 * 180 = 135 and USD -> EUR -> JPY gives 0.9 * 150 = 135, but the longer route USD -> EUR -> GBP -> JPY gives 0.9 * 0.85 * 180 = 137.7, which is the best.
Example 2
- Input:
- rates = [["USD", "EUR", 0.9]], source = "EUR", target = "USD"
- Output:
- -1.0
- Explanation
- Quotes only work in the direction listed. There is a USD -> EUR quote but no EUR -> USD quote, so USD cannot be reached.
Example 3
- Input:
- rates = [["BTC", "ETH", 20.0], ["ETH", "BTC", 0.049]], source = "BTC", target = "BTC"
- Output:
- 1.0
- Explanation
- Converting a currency to itself needs no trades, so the answer is
1.0.
Constraints
0 <= rates.length <= 2000- At most
100distinct currencies appear 0 < rate <= 10^6- No conversion cycle has a rate product of
1or more sourceandtargetare non-empty strings