Skip to content

3387. Maximize Amount After Two Days of Conversions

  • Time: $O(|\texttt{pairs}|^2)$
  • Space: $O(|\texttt{pairs}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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]);
      }
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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);
      }
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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)