129. Currency Conversion

Currency Conversion

You are given a currency conversion map and need to convert an amount from one currency to another.

Each conversion rate represents a directed edge in a graph:
if rates.get(i) is "USD,INR,83.0", then 1 USD = 83.0 INR.

A conversion may require one or more intermediate currencies. For example, if there is no direct conversion from USD to JPY, you may still be able to convert through another path such as USD -> EUR -> JPY.

If multiple valid conversion paths exist, choose the path that yields the maximum converted value.

A conversion path must never contain a cycle. In other words, no currency may appear more than once in the same conversion path.

Each amount and return value is considered only up to at most 2 decimal places. Any digits after the first 2 decimal places must be truncated.

Return the converted amount from sourceCurrency to targetCurrency.

If no valid conversion path exists, return -1.0.

If sourceCurrency and targetCurrency are the same, return the original amount truncated to 2 decimal places.

Method Signature

double convertCurrency(List<String> rates, String sourceCurrency, String targetCurrency, double amount)

rates is a non-null list of conversion entries.
Each entry in rates is in the format from,to,rate.
from and to are currency codes.
rate is a positive decimal number.
The graph should be treated as directed unless the reverse conversion is explicitly provided in rates.
A valid conversion path may use one or more edges from sourceCurrency to targetCurrency.
No currency may appear more than once in a valid conversion path.
If multiple valid paths exist, return the maximum converted value among all such paths.
If no valid path exists, return -1.0.
If sourceCurrency.equals(targetCurrency), return amount truncated to 2 decimal places.
amount - the amount to convert.

Returns

Returns the maximum converted amount as a double among all valid non-cyclic conversion paths.
The returned value must be truncated to at most 2 decimal places.
If no valid conversion path exists, returns -1.0.

Constraints

1 ≤ rates.size() ≤ 1000
Each string in rates contains exactly three comma-separated parts: from, to, and rate.
from.length() > 0 and to.length() > 0
rate > 0
amount >= 0
amount has at most 2 decimal places.
Every returned amount must be truncated to at most 2 decimal places.
Currency codes are case-sensitive.
There may be multiple currencies and multiple valid paths in the graph.
A valid answer must be computed using a non-cyclic path only.
You may assume the input format is valid.

Notes

This is a graph problem.
Each currency is a node.
Each conversion rule is a directed edge with multiplicative weight.
A path conversion result is the product of all rates along that path, multiplied by amount.
Among all valid non-cyclic paths, choose the one with the maximum final truncated value.

Examples

Example 1

Input:

convertCurrency(rates = List.of("USD,EUR,0.9", "EUR,INR,90.0"), sourceCurrency = "USD", targetCurrency = "INR", amount = 10.0)

Output:
810.0

Explanation:
The valid path is USD -> EUR -> INR.
Converted amount = 10.0 * 0.9 * 90.0 = 810.0.

Example 2

Input:

convertCurrency(rates = List.of("USD,GBP,0.8", "GBP,JPY,190.0"), sourceCurrency = "USD", targetCurrency = "JPY", amount = 5.0)

Output:
760.0

Explanation:
The valid path is USD -> GBP -> JPY.
Converted amount = 5.0 * 0.8 * 190.0 = 760.0.

Example 3

Input:

convertCurrency(rates = List.of("USD,EUR,0.9", "EUR,GBP,0.85"), sourceCurrency = "USD", targetCurrency = "JPY", amount = 7.0)

Output:
-1.0

Explanation:
There is no valid path from USD to JPY.

Example 4

Input:
convertCurrency(rates = List.of("USD,INR,83.0"), sourceCurrency = "INR", targetCurrency = "INR", amount = 250.56)

Output:
250.56

Explanation:
Source and target currencies are the same, so the original amount is returned.

Example 5

Input:

convertCurrency(rates = List.of("USD,EUR,0.9", "EUR,JPY,160.0", "USD,JPY,140.0"), sourceCurrency = "USD", targetCurrency = "JPY", amount = 2.0)

Output:
288.0

Explanation:
There are two valid paths:
USD -> JPY = 2.0 * 140.0 = 280.0
USD -> EUR -> JPY = 2.0 * 0.9 * 160.0 = 288.0
Choose the maximum value, so the answer is 288.0.

Example 6

Input:

convertCurrency(rates = List.of("USD,EUR,0.915", "EUR,INR,90.127"), sourceCurrency = "USD", targetCurrency = "INR", amount = 10.99)

Output:
906.48

Explanation:
The valid path is USD -> EUR -> INR.
Raw value = 10.99 * 0.915 * 90.127 = 906.48265955.
After truncating everything after 2 decimal places, the result is 906.48.

Example 7

Input:

convertCurrency(rates = List.of("USD,EUR,0.9", "EUR,USD,1.1", "EUR,JPY,150.0"), sourceCurrency = "USD", targetCurrency = "JPY", amount = 1.0)

Output:
135.0

Explanation:
A path such as USD -> EUR -> USD -> ... is not allowed because it repeats a currency and forms a cycle.
The valid non-cyclic path is USD -> EUR -> JPY.
Converted amount = 1.0 * 0.9 * 150.0 = 135.0.