Maximize Amount After Two Days of Conversions - Video Solutions
Leetcode 3387 | Maximize Amount After Two Days of Conversions | Weekly Contest 428
Maximize Amount After Two Days of Conversions - Video Solution
Watch 4 video solutions for Maximize Amount After Two Days of Conversions, a medium level problem involving Array, String, Depth-First Search. This walkthrough by Road To FAANG has 2,104 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are given a string initialCurrency, and you start with 1.0 of initialCurrency.
You are also given four arrays with currency pairs (strings) and rates (real numbers):
pairs1[i] = [startCurrencyi, targetCurrencyi]denotes that you can convert fromstartCurrencyitotargetCurrencyiat a rate ofrates1[i]on day 1.pairs2[i] = [startCurrencyi, targetCurrencyi]denotes that you can convert fromstartCurrencyitotargetCurrencyiat a rate ofrates2[i]on day 2.- Also, each
targetCurrencycan be converted back to its correspondingstartCurrencyat a rate of1 / rate.
You can perform any number of conversions, including zero, using rates1 on day 1, followed by any number of additional conversions, including zero, using rates2 on day 2.
Return the maximum amount of initialCurrency you can have after performing any number of conversions on both days in order.
Note: Conversion rates are valid, and there will be no contradictions in the rates for either day. The rates for the days are independent of each other.
Example 1:
Input: initialCurrency = "EUR", pairs1 = [["EUR","USD"],["USD","JPY"]], rates1 = [2.0,3.0], pairs2 = [["JPY","USD"],["USD","CHF"],["CHF","EUR"]], rates2 = [4.0,5.0,6.0]
Output: 720.00000
Explanation:
To get the maximum amount of EUR, starting with 1.0 EUR:
- On Day 1:
- Convert EUR to USD to get 2.0 USD.
- Convert USD to JPY to get 6.0 JPY.
- On Day 2:
- Convert JPY to USD to get 24.0 USD.
- Convert USD to CHF to get 120.0 CHF.
- Finally, convert CHF to EUR to get 720.0 EUR.
Example 2:
Input: initialCurrency = "NGN", pairs1 = [["NGN","EUR"]], rates1 = [9.0], pairs2 = [["NGN","EUR"]], rates2 = [6.0]
Output: 1.50000
Explanation:
Converting NGN to EUR on day 1 and EUR to NGN using the inverse rate on day 2 gives the maximum amount.
Example 3:
Input: initialCurrency = "USD", pairs1 = [["USD","EUR"]], rates1 = [1.0], pairs2 = [["EUR","JPY"]], rates2 = [10.0]
Output: 1.00000
Explanation:
In this example, there is no need to make any conversions on either day.
Constraints:
1 <= initialCurrency.length <= 3initialCurrencyconsists only of uppercase English letters.1 <= n == pairs1.length <= 101 <= m == pairs2.length <= 10pairs1[i] == [startCurrencyi, targetCurrencyi]pairs2[i] == [startCurrencyi, targetCurrencyi]1 <= startCurrencyi.length, targetCurrencyi.length <= 3startCurrencyiandtargetCurrencyiconsist only of uppercase English letters.rates1.length == nrates2.length == m1.0 <= rates1[i], rates2[i] <= 10.0- The input is generated such that there are no contradictions or cycles in the conversion graphs for either day.
- The input is generated such that the output is at most
5 * 1010.
Approach Overview
Problem Overview: You start with 1 unit of an initial currency. Day 1 and Day 2 each provide a set of currency conversion pairs with exchange rates. You may perform multiple conversions per day. The goal is to end with the maximum possible amount of the initial currency after completing conversions across both days.
Approach 1: Brute Force Conversion Exploration (Exponential Time)
A naive strategy explores every possible sequence of conversions on Day 1, then repeats the same exploration for Day 2. Each conversion multiplies the current amount by the exchange rate. Because currencies can connect in many ways, the number of possible paths grows exponentially. This approach models the problem as a graph and recursively tries all paths without pruning. Time complexity becomes O(b^d) where b is the branching factor of conversions and d is path depth, with O(d) recursion space. It works only for extremely small inputs and mainly helps verify correctness.
Approach 2: Graph Traversal with DFS/BFS (O(V + E))
Treat each day's conversions as a weighted graph where nodes are currencies and edges store the conversion rate. Since converting A → B with rate r implies B → A with rate 1/r, both directions are added to the graph. First traverse the Day 1 graph starting from the initial currency and compute the maximum amount reachable for every currency. A Depth-First Search or Breadth-First Search propagates the best multiplicative value across edges while updating the maximum seen for each node.
Next evaluate Day 2. For every currency reachable after Day 1, run another traversal on the Day 2 graph to determine the maximum amount of the initial currency obtainable from that currency. Multiply the Day 1 amount by the best Day 2 conversion result and keep the global maximum. Because the graphs are small, each traversal runs in O(V + E) time with O(V) space for visited states.
This method works because currency conversions form a weighted graph where the objective is maximizing a product along paths. Tracking the best amount per currency prevents unnecessary revisits and keeps the search linear relative to the graph size.
Recommended for interviews: Interviewers expect the graph modeling approach with DFS or BFS. The brute force explanation shows you recognize the search space, but representing currencies as graph nodes and propagating the maximum product demonstrates stronger algorithmic thinking.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Conversion Paths | Exponential | O(d) | Only for conceptual understanding or extremely small graphs |
| Graph Traversal with DFS/BFS | O(V + E) | O(V) | General case; efficiently explores conversion graphs for both days |
| Graph Traversal with Memoization | O(V + E) | O(V) | Useful when multiple currencies require repeated Day 2 searches |