Optimized Portfolio Conversion with Fee Budget
Groww is committed to providing users with efficient financial tools. A common need is to convert one asset into another, which may involve a series of intermediate trades. Each trade incurs both a transaction fee and a time delay (e.g., for settlement). This problem challenges you to find the most time-efficient sequence of trades to convert a starting asset into a target asset, while ensuring the total transaction fees incurred do not exceed a specified budget. This capability is crucial for optimizing portfolio rebalancing and ensuring cost-effective asset management for our users.
Implement a function minTimeAssetConversion that determines the minimum total time required to convert a startAsset to a targetAsset through a series of trades. The cumulative feeCost of all trades in the path must not exceed maxFeeBudget.
maxFeeBudget, return -1.Function Signature:
function minTimeAssetConversion(numAssets: number, trades: number[][], startAsset: number, targetAsset: number, maxFeeBudget: number): number
Parameters:
numAssets: An integer representing the total number of distinct assets, indexed from 0 to numAssets - 1.trades: An array of arrays, where each inner array [u, v, time, fee] represents a possible direct trade: converting asset u to asset v.
u: The source asset (integer 0 to numAssets - 1).v: The destination asset (integer 0 to numAssets - 1).time: The time cost (integer) incurred for this trade.fee: The transaction fee (integer) incurred for this trade.startAsset: The initial asset (integer 0 to numAssets - 1).targetAsset: The desired final asset (integer 0 to numAssets - 1).maxFeeBudget: An integer representing the maximum total transaction fee allowed for the entire conversion path.Return Value:
number representing the minimum total time cost to convert startAsset to targetAsset within the maxFeeBudget.-1 if no such valid conversion path exists.u to v if specified in trades. Trades are one-way.u and v (e.g., different brokers offering different time/fee combinations). You should consider all such options.startAsset and targetAsset can be the same. In this case, if startAsset === targetAsset and maxFeeBudget >= 0, the minimum time is 0.Examples
Example 1
Input:
numAssets = 3, trades = [[0, 1, 10, 5], [1, 2, 8, 3]], startAsset = 0, targetAsset = 2, maxFeeBudget = 10
Output:
18
Note:
Path 0 -> 1 -> 2: Total time = 10 + 8 = 18. Total fee = 5 + 3 = 8. Since 8 <= 10, this path is valid and its time is 18.
Example 2
Input:
numAssets = 4, trades = [[0, 1, 10, 5], [0, 2, 2, 8], [1, 3, 15, 2], [2, 3, 5, 6]], startAsset = 0, targetAsset = 3, maxFeeBudget = 10
Output:
25
Note:
Path 0 -> 1 -> 3: Total time = 10 + 15 = 25. Total fee = 5 + 2 = 7. (Valid) Path 0 -> 2 -> 3: Total time = 2 + 5 = 7. Total fee = 8 + 6 = 14. (Invalid, fee 14 > budget 10) The minimum valid time is 25.
Example 3
Input:
numAssets = 3, trades = [[0, 1, 10, 5], [1, 2, 8, 3]], startAsset = 0, targetAsset = 2, maxFeeBudget = 7
Output:
-1
Note:
The only path 0 -> 1 -> 2 has a total fee of 8, which exceeds the maxFeeBudget of 7. No valid path exists.
Example 4
Input:
numAssets = 3, trades = [[0, 2, 20, 10], [0, 1, 5, 2], [1, 2, 5, 3]], startAsset = 0, targetAsset = 2, maxFeeBudget = 10
Output:
10
Note:
Path 0 -> 2: Total time = 20, total fee = 10. (Valid) Path 0 -> 1 -> 2: Total time = 5 + 5 = 10, total fee = 2 + 3 = 5. (Valid) The minimum valid time among these is 10.
Constraints
1 <= numAssets <= 1000 <= trades.length <= 5000trade in trades is [u, v, time, fee] where:
0 <= u, v < numAssets0 <= time <= 10000 <= fee <= 1000 <= startAsset, targetAsset < numAssets0 <= maxFeeBudget <= 500Loading editor...