3387. Maximize Amount After Two Days of Conversions LeetCode Solution

Last updated: March 6, 2025

In this guide, you will get 3387. Maximize Amount After Two Days of Conversions LeetCode Solution with the best time and space complexity. The solution to Maximize Amount After Two Days of Conversions problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Maximize Amount After Two Days of Conversions solution in C++
  4. Maximize Amount After Two Days of Conversions solution in Java
  5. Maximize Amount After Two Days of Conversions solution in Python
  6. Additional Resources
3387. Maximize Amount After Two Days of Conversions LeetCode Solution image

Problem Statement of Maximize Amount After Two Days of Conversions

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 from startCurrencyi to targetCurrencyi at a rate of rates1[i] on day 1.
pairs2[i] = [startCurrencyi, targetCurrencyi] denotes that you can convert from startCurrencyi to targetCurrencyi at a rate of rates2[i] on day 2.
Also, each targetCurrency can be converted back to its corresponding startCurrency at a rate of 1 / 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 <= 3
initialCurrency consists only of uppercase English letters.
1 <= n == pairs1.length <= 10
1 <= m == pairs2.length <= 10
pairs1[i] == [startCurrencyi, targetCurrencyi]
pairs2[i] == [startCurrencyi, targetCurrencyi]
1 <= startCurrencyi.length, targetCurrencyi.length <= 3
startCurrencyi and targetCurrencyi consist only of uppercase English letters.
rates1.length == n
rates2.length == m
1.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.

Complexity Analysis

  • Time Complexity: O(|\texttt{pairs}|^2)
  • Space Complexity: O(|\texttt{pairs}|)

3387. Maximize Amount After Two Days of Conversions LeetCode Solution in C++

class Solution {
 public:
  double maxAmount(string initialCurrency, vector<vector<string>>& pairs1,
                   vector<double>& rates1, vector<vector<string>>& pairs2,
                   vector<double>& rates2) {
    // dp[currency] := the maximum amount of money to convert to `currency`
    unordered_map<string, double> dp{{initialCurrency, 1}};
    bellman(dp, pairs1, rates1);
    bellman(dp, pairs2, rates2);
    return dp[initialCurrency];
  }

 private:
  void bellman(unordered_map<string, double>& dp,
               const vector<vector<string>>& pairs,
               const vector<double>& rates) {
    for (int relax = 0; relax < pairs.size(); ++relax)
      for (int i = 0; i < pairs.size(); ++i) {
        const string start = pairs[i][0];
        const string target = pairs[i][1];
        dp[target] = max(dp[target], dp[start] * rates[i]);
        dp[start] = max(dp[start], dp[target] / rates[i]);
      }
  }
};
/* code provided by PROGIEZ */

3387. Maximize Amount After Two Days of Conversions LeetCode Solution in Java

class Solution {
  public double maxAmount(String initialCurrency, List<List<String>> pairs1, double[] rates1,
                          List<List<String>> pairs2, double[] rates2) {
    // dp[currency] := the maximum amount of money to convert to `currency`
    Map<String, Double> dp = new HashMap<>();
    dp.put(initialCurrency, 1.0);
    bellman(dp, pairs1, rates1);
    bellman(dp, pairs2, rates2);
    return dp.get(initialCurrency);
  }

  private void bellman(Map<String, Double> dp, List<List<String>> pairs, double[] rates) {
    for (int relax = 0; relax < pairs.size(); ++relax)
      for (int i = 0; i < pairs.size(); ++i) {
        final String start = pairs.get(i).get(0);
        final String target = pairs.get(i).get(1);
        dp.merge(target, dp.getOrDefault(start, 0.0) * rates[i], Double::max);
        dp.merge(start, dp.getOrDefault(target, 0.0) / rates[i], Double::max);
      }
  }
}
// code provided by PROGIEZ

3387. Maximize Amount After Two Days of Conversions LeetCode Solution in Python

class Solution:
  def maxAmount(
      self,
      initialCurrency: str,
      pairs1: list[list[str]],
      rates1: list[float],
      pairs2: list[list[str]],
      rates2: list[float]
  ) -> float:
    # dp[currency] := the maximum amount of money to convert to `currency`
    dp: dict[str, float] = collections.defaultdict(float)
    dp[initialCurrency] = 1.0
    self._bellman(dp, pairs1, rates1)
    self._bellman(dp, pairs2, rates2)
    return dp[initialCurrency]

  def _bellman(
      self,
      dp: dict[str, float],
      pairs: list[list[str]],
      rates: list[float]
  ) -> None:
    for _ in range(len(pairs)):
      for (start, target), rate in zip(pairs, rates):
        dp[target] = max(dp[target], dp[start] * rate)
        dp[start] = max(dp[start], dp[target] / rate)
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.