# Maximize Amount After Two Days of Conversions **Difficulty:** MEDIUM [External](https://leetcode.com/problems/maximize-amount-after-two-days-of-conversions) Canonical: https://scaleengineer.com/dsa/problems/maximize-amount-after-two-days-of-conversions **Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search) **Data structures:** Array, String, Graph **Companies:** [Rippling](https://scaleengineer.com/companies/rippling) --- ## Problem 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`. # Approaches ## All-Pairs Maximum Product using Floyd-Warshall This approach models the currency conversions as a graph problem where currencies are nodes and conversion rates are edge weights. The core idea is to find the maximum conversion rates between all pairs of currencies for each day. The Floyd-Warshall algorithm, typically used for all-pairs shortest paths, is adapted to find maximum product paths. We execute this algorithm for both Day 1 and Day 2's conversion rates. Finally, we iterate through all possible intermediate currencies to identify the conversion sequence that maximizes the final amount of `initialCurrency`. **Time:** O(C^3 + (P1 + P2) * L), where `C` is the number of unique currencies, `P1` and `P2` are the number of pairs, and `L` is the max currency string length. The O(C^3) term from two runs of Floyd-Warshall dominates. · **Space:** O(C^2 + C * L), where `C` is the number of unique currencies and `L` is the max currency string length. O(C^2) is for the two distance matrices, and O(C * L) is for the currency map. **Pros:** Conceptually straightforward application of a standard graph algorithm.; Robust and would work even if the graph contained cycles (as long as there are no arbitrage cycles with a product greater than 1). **Cons:** Higher time complexity of O(C^3) compared to a traversal-based approach, where C is the number of currencies.; Does not leverage the problem's "no cycles" guarantee, which permits a more efficient solution. ### Explanation First, we gather all unique currency names from the input and assign a unique integer index to each. This allows us to use matrices for our calculations. We create a distance matrix `dist1` for Day 1, where `dist1[i][j]` will store the maximum conversion rate from currency `i` to `j`. We initialize this matrix by setting `dist1[i][i] = 1.0` for all `i`, and `dist1[i][j] = 0.0` for `i != j`. Then, we populate it with the initial rates from `pairs1`: for a pair `(u, v)` with rate `r`, we set `dist1[u_idx][v_idx] = r` and `dist1[v_idx][u_idx] = 1.0 / r`. Next, we apply a modified Floyd-Warshall algorithm on `dist1`. The standard update rule `dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])` is changed to `dist1[i][j] = max(dist1[i][j], dist1[i][k] * dist1[k][j])`. This process iteratively finds the best conversion path between any two currencies by considering every other currency as a potential intermediate stop. We repeat the entire process for Day 2's rates to compute a `dist2` matrix. Finally, to find the maximum possible amount, we consider every currency `C` as a potential intermediate currency held at the end of Day 1. The path is `initialCurrency -> C` on Day 1, followed by `C -> initialCurrency` on Day 2. The final amount for this path is `1.0 * dist1[initial_idx][C_idx] * dist2[C_idx][initial_idx]`. We iterate through all currencies as `C` and take the maximum result. The case of performing no conversions is naturally handled when `C` is the `initialCurrency` itself, yielding a rate of `1.0 * 1.0 = 1.0`. ```java import java.util.*; class Solution { public double maximizeAmount(String initialCurrency, String[][] pairs1, double[] rates1, String[][] pairs2, double[] rates2) { Set currencySet = new HashSet<>(); currencySet.add(initialCurrency); for (String[] pair : pairs1) { currencySet.add(pair[0]); currencySet.add(pair[1]); } for (String[] pair : pairs2) { currencySet.add(pair[0]); currencySet.add(pair[1]); } List currencyList = new ArrayList<>(currencySet); Map currencyMap = new HashMap<>(); for (int i = 0; i < currencyList.size(); i++) { currencyMap.put(currencyList.get(i), i); } int n = currencyList.size(); int initialIdx = currencyMap.get(initialCurrency); double[][] dist1 = buildAndRunFloydWarshall(n, pairs1, rates1, currencyMap); double[][] dist2 = buildAndRunFloydWarshall(n, pairs2, rates2, currencyMap); double maxAmount = 1.0; for (int i = 0; i < n; i++) { // i is the index for the intermediate currency if (dist1[initialIdx][i] > 0 && dist2[i][initialIdx] > 0) { double currentAmount = dist1[initialIdx][i] * dist2[i][initialIdx]; maxAmount = Math.max(maxAmount, currentAmount); } } return maxAmount; } private double[][] buildAndRunFloydWarshall(int n, String[][] pairs, double[] rates, Map currencyMap) { double[][] dist = new double[n][n]; for (int i = 0; i < n; i++) { dist[i][i] = 1.0; } for (int i = 0; i < pairs.length; i++) { int u = currencyMap.get(pairs[i][0]); int v = currencyMap.get(pairs[i][1]); double rate = rates[i]; dist[u][v] = rate; dist[v][u] = 1.0 / rate; } for (int k = 0; k < n; k++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (dist[i][k] > 0 && dist[k][j] > 0) { dist[i][j] = Math.max(dist[i][j], dist[i][k] * dist[k][j]); } } } } return dist; } } ``` ### Algorithm - Create a mapping from each unique currency string to an integer index `0..N-1`, where `N` is the number of unique currencies. - Initialize an `N x N` matrix `dist1` for Day 1 rates. Set `dist1[i][i] = 1.0` and other entries to `0.0` (representing no direct path). - Populate `dist1` with the given rates from `pairs1`. For a conversion `(u, v)` with rate `r`, set `dist1[u_idx][v_idx] = r` and `dist1[v_idx][u_idx] = 1/r`. - Run the Floyd-Warshall algorithm on `dist1` with a modified update rule to find maximum product paths: `dist1[i][j] = max(dist1[i][j], dist1[i][k] * dist1[k][j])`. - Repeat the initialization and Floyd-Warshall steps for Day 2 rates to compute a `dist2` matrix. - Initialize `maxAmount = 1.0`. - Let `initialIdx` be the index of `initialCurrency`. - Iterate through all currencies `k` from `0` to `N-1`. This `k` represents the intermediate currency after Day 1. - Calculate the total amount for this path: `amount = dist1[initialIdx][k] * dist2[k][initialIdx]`. - Update `maxAmount = max(maxAmount, amount)`. - Return `maxAmount`. ## Graph Traversal from a Single Source (DFS/BFS) This approach takes full advantage of the problem's guarantee that there are no cycles in the conversion graphs. This simplifies the graph for each day to a forest (a collection of trees). In a tree, the path between any two connected nodes is unique. Consequently, we can find the necessary conversion rates by performing a single, simple graph traversal (like Breadth-First Search or Depth-First Search) starting from the `initialCurrency` for each day's graph, which is more efficient than an all-pairs algorithm. **Time:** O((P1 + P2 + C) * L), where `C` is the number of currencies, `P1` and `P2` are pair counts, and `L` is string length. This covers building the currency map, constructing two graphs, and traversing each one once. · **Space:** O(C + P1 + P2 + C * L), where `C` is the number of currencies, `P1` and `P2` are pair counts, and `L` is string length. This space is for the adjacency lists, rate arrays, and the currency map. **Pros:** Highly efficient in terms of time and space complexity.; Directly utilizes the problem constraints ("no cycles") for a simple and optimized solution. **Cons:** This approach relies heavily on the problem's "no cycles" guarantee. If the graph could have cycles, it would require a more complex algorithm like Bellman-Ford to ensure correctness. ### Explanation First, we identify all unique currencies and map them to integer indices for efficient processing. For Day 1, we build a graph using an adjacency list from `pairs1` and `rates1`. Since conversions are bidirectional, for each pair `(u, v)` with rate `r`, we add an edge from `u` to `v` with weight `r` and an edge from `v` to `u` with weight `1/r`. We then perform a single traversal (BFS is a good choice) starting from the `initialCurrency` node on the Day 1 graph. During this traversal, we compute the cumulative product of rates from `initialCurrency` to every other reachable currency. These rates are stored in an array, `day1_rates`, where `day1_rates[i]` holds the amount of currency `i` we get from 1 unit of `initialCurrency`. We repeat this exact process for Day 2, building its graph and running a traversal from `initialCurrency` to compute `day2_rates`. With these two rate arrays, we can find the maximum final amount. We iterate through every currency `C` as a potential intermediate currency. The conversion path is `initialCurrency -> C` on Day 1, and then `C -> initialCurrency` on Day 2. - The rate for `initialCurrency -> C` on Day 1 is directly available as `day1_rates[C_idx]`. - The rate for `C -> initialCurrency` on Day 2 is the reciprocal of the rate for `initialCurrency -> C` on Day 2 (due to the tree structure), which is `1.0 / day2_rates[C_idx]`. The total amount for using `C` as an intermediate is `1.0 * day1_rates[C_idx] * (1.0 / day2_rates[C_idx])`. We compute this for all currencies `C` reachable on both days and find the maximum. We initialize our max amount to `1.0` to handle the case of no conversions. ```java import java.util.*; class Solution { public double maximizeAmount(String initialCurrency, String[][] pairs1, double[] rates1, String[][] pairs2, double[] rates2) { Set currencySet = new HashSet<>(); currencySet.add(initialCurrency); for (String[] pair : pairs1) { currencySet.add(pair[0]); currencySet.add(pair[1]); } for (String[] pair : pairs2) { currencySet.add(pair[0]); currencySet.add(pair[1]); } List currencyList = new ArrayList<>(currencySet); Map currencyMap = new HashMap<>(); for (int i = 0; i < currencyList.size(); i++) { currencyMap.put(currencyList.get(i), i); } int n = currencyList.size(); int initialIdx = currencyMap.get(initialCurrency); double[] day1Rates = calculateRatesFromSource(n, initialIdx, pairs1, rates1, currencyMap); double[] day2Rates = calculateRatesFromSource(n, initialIdx, pairs2, rates2, currencyMap); double maxAmount = 1.0; for (int i = 0; i < n; i++) { if (day1Rates[i] > 0 && day2Rates[i] > 0) { double currentAmount = day1Rates[i] / day2Rates[i]; maxAmount = Math.max(maxAmount, currentAmount); } } return maxAmount; } private double[] calculateRatesFromSource(int n, int sourceIdx, String[][] pairs, double[] rates, Map currencyMap) { Map>> adj = new HashMap<>(); for (int i = 0; i < pairs.length; i++) { int u = currencyMap.get(pairs[i][0]); int v = currencyMap.get(pairs[i][1]); double rate = rates[i]; adj.computeIfAbsent(u, k -> new ArrayList<>()).add(new AbstractMap.SimpleEntry<>(v, rate)); adj.computeIfAbsent(v, k -> new ArrayList<>()).add(new AbstractMap.SimpleEntry<>(u, 1.0 / rate)); } double[] resultRates = new double[n]; Queue> queue = new LinkedList<>(); queue.offer(new AbstractMap.SimpleEntry<>(sourceIdx, 1.0)); resultRates[sourceIdx] = 1.0; while (!queue.isEmpty()) { Map.Entry current = queue.poll(); int u = current.getKey(); double currentRate = current.getValue(); if (adj.containsKey(u)) { for (Map.Entry neighbor : adj.get(u)) { int v = neighbor.getKey(); double edgeRate = neighbor.getValue(); if (resultRates[v] == 0.0 && v != sourceIdx) { // Not visited yet resultRates[v] = currentRate * edgeRate; queue.offer(new AbstractMap.SimpleEntry<>(v, resultRates[v])); } } } } return resultRates; } } ``` ### Algorithm - Create a mapping from each unique currency string to an integer index `0..N-1`. - **Day 1 Rates**: - Build an adjacency list representation of the Day 1 graph. - Create a `rates1` array of size `N`, initialized to 0. - Run a graph traversal (like BFS or DFS) starting from `initialCurrency`'s index. Populate `rates1` with the calculated conversion rates from `initialCurrency` to all reachable currencies. - **Day 2 Rates**: - Build an adjacency list for the Day 2 graph. - Create a `rates2` array of size `N`, initialized to 0. - Run a similar traversal on the Day 2 graph, starting from `initialCurrency`, to populate `rates2`. - **Calculate Max Amount**: - Initialize `maxAmount = 1.0`. - For each currency index `i` from `0` to `N-1`: - If currency `i` is reachable on both days (i.e., `rates1[i] > 0` and `rates2[i] > 0`): - The rate for `initialCurrency -> i` on Day 1 is `rates1[i]`. - The rate for `i -> initialCurrency` on Day 2 is `1.0 / rates2[i]`. - Calculate the total amount: `amount = rates1[i] / rates2[i]`. - Update `maxAmount = max(maxAmount, amount)`. - Return `maxAmount`. # Solutions ### Java ```java class Solution { public double maxAmount(String initialCurrency, List> pairs1, double[] rates1, List> pairs2, double[] rates2) { Map d1 = build(pairs1, rates1, initialCurrency); Map d2 = build(pairs2, rates2, initialCurrency); double ans = 0; for (Map.Entry entry : d2.entrySet()) { String currency = entry.getKey(); double rate = entry.getValue(); if (d1.containsKey(currency)) { ans = Math.max(ans, d1.get(currency) / rate); } } return ans; } private Map build(List> pairs, double[] rates, String init) { Map>> g = new HashMap<>(); Map d = new HashMap<>(); for (int i = 0; i < pairs.size(); ++i) { String a = pairs.get(i).get(0); String b = pairs.get(i).get(1); double r = rates[i]; g.computeIfAbsent(a, k->new ArrayList<>()).add(new Pair<>(b, r)); g.computeIfAbsent(b, k->new ArrayList<>()).add(new Pair<>(a, 1 / r)); } dfs(g, d, init, 1.0); return d; } private void dfs(Map>> g, Map d, String a, double v) { if (d.containsKey(a)) { return; } d.put(a, v); for (Pair pair : g.getOrDefault(a, List.of())) { String b = pair.getKey(); double r = pair.getValue(); if (!d.containsKey(b)) { dfs(g, d, b, v * r); } } } } ``` ### CPP ```cpp class Solution { public: double maxAmount(string initialCurrency, vector> &pairs1, vector &rates1, vector> &pairs2, vector &rates2) { unordered_map d1 = build(pairs1, rates1, initialCurrency); unordered_map d2 = build(pairs2, rates2, initialCurrency); double ans = 0; for (const auto &[currency, rate] : d2) { if (d1.find(currency) != d1.end()) { ans = max(ans, d1[currency] / rate); } } return ans; } private: unordered_map build(vector> &pairs, vector &rates, const string &init) { unordered_map>> g; unordered_map d; for (int i = 0; i < pairs.size(); ++i) { const string &a = pairs[i][0]; const string &b = pairs[i][1]; double r = rates[i]; g[a].push_back({b, r}); g[b].push_back({a, 1 / r}); } auto dfs = [&](this auto &&dfs, const string &a, double v) -> void { if (d.find(a) != d.end()) { return; } d[a] = v; for (const auto &[b, r] : g[a]) { if (d.find(b) == d.end()) { dfs(b, v * r); } } }; dfs(init, 1.0); return d; } }; ``` ### Python ```python class Solution: def maxAmount(self, initialCurrency: str, pairs1: List[List[str]], rates1: List[float], pairs2: List[List[str]], rates2: List[float], ) -> float: d1 = self . build(pairs1, rates1, initialCurrency) d2 = self . build(pairs2, rates2, initialCurrency) return max(d1 . get(a, 0) / r2 for a, r2 in d2 . items()) def build(self, pairs: List[List[str]], rates: List[float], init: str) -> Dict[str, float]: def dfs(a: str, v: float): d[a] = v for b, r in g[a]: if b not in d: dfs(b, v * r) g = defaultdict(list) for (a, b), r in zip(pairs, rates): g[a]. append((b, r)) g[b]. append((a, 1 / r)) d = {} dfs(init, 1) return d ```