Optimal Asset Conversion Path
In the dynamic world of financial trading, clients often need to convert one asset into another, sometimes requiring multiple intermediate conversions through different exchanges or brokers. Each direct conversion comes with a transaction fee. To maximize returns, it's crucial to find the sequence of conversions that incurs the minimum total fee. This problem challenges you to model and solve this scenario, identifying the optimal path for asset conversion.
Your task is to implement a function that calculates the minimum total transaction fee required to convert a startAsset to an endAsset.
startAsset to the endAsset.startAsset is the same as the endAsset, or where no conversion path exists between the given assets.Function Signature:
function findOptimalConversionPath(
assets: string[],
exchangeRates: [string, string, number][],
startAsset: string,
endAsset: string
): number
assets: An array of strings, where each string is the unique identifier for an asset (e.g., "INR", "USD", "BTC"). These are all possible nodes in your graph.exchangeRates: An array of tuples (or arrays) [asset1, asset2, fee]. Each tuple represents a direct conversion from asset1 to asset2 with a non-negative fee. This implies a directed edge from asset1 to asset2 with the specified fee as its weight.startAsset: A string representing the asset you initially possess.endAsset: A string representing the asset you wish to obtain.Returns:
number representing the minimum total transaction fee to convert startAsset to endAsset. Return -1 if no path exists from startAsset to endAsset.[A, B, fee] means you can convert A to B. It does not imply you can convert B to A, unless explicitly specified by another entry [B, A, anotherFee] in exchangeRates.startAsset is the same as endAsset, the fee is 0.startAsset and endAsset strings are present in the assets array, and all asset1/asset2 in exchangeRates are also valid assets.Examples
Example 1
Input:
assets = ["INR", "USD", "EUR", "GBP"], exchangeRates = [["INR", "USD", 10], ["USD", "EUR", 5], ["EUR", "GBP", 7], ["INR", "EUR", 18]], startAsset = "INR", endAsset = "GBP"
Output:
22
Note:
Path 1: INR -> USD (10) -> EUR (5) -> GBP (7). Total fee = 10 + 5 + 7 = 22. Path 2: INR -> EUR (18) -> GBP (7). Total fee = 18 + 7 = 25. The minimum fee is 22.
Example 2
Input:
assets = ["INR", "USD", "JPY"], exchangeRates = [["INR", "USD", 10]], startAsset = "INR", endAsset = "JPY"
Output:
-1
Note:
There is no path to convert INR to JPY. Only INR to USD is possible.
Example 3
Input:
assets = ["INR", "USD"], exchangeRates = [["INR", "USD", 10]], startAsset = "INR", endAsset = "INR"
Output:
0
Note:
The start asset is the same as the end asset, so no conversion is needed, and the fee is 0.
Constraints
1 <= assets.length <= 100 (Number of distinct assets)0 <= exchangeRates.length <= 1000 (Number of direct conversion routes)0 <= fee <= 1000 for each conversion. Fees are non-negative integers.startAsset and endAsset will always be valid strings present in the assets array."INR", "USD").Loading editor...