Maximize Amount After Two Days of Conversions

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


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

1
2
3
4
5
6


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

1
2
3
4
5


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.

Examples

Solution

Method 1 – Graph Traversal (Floyd-Warshall for All-Pairs Max Product)

Intuition

Each day’s conversions form a directed weighted graph. On day 1, we can convert currencies as much as we want, and similarly on day 2. The best strategy is to maximize the amount of any currency at the end of day 1, then maximize the amount of the initial currency at the end of day 2. We use the Floyd-Warshall algorithm to compute the best conversion rates between all pairs for both days.

Approach

Build a graph for day 1 and day 2, including both directions for each pair (with reciprocal rates).
Use Floyd-Warshall to compute the maximum product (conversion rate) between all pairs for both days.
For each currency, compute the maximum amount of initialCurrency we can get by converting to that currency on day 1, then back to initialCurrency on day 2.
Return the maximum amount found.

Code

 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
27
28
29
30
31
32
33
34
35
36


class Solution {
public:
    double maximizeAmount(string initialCurrency, vector<vector<string>>& pairs1, vector<double>& rates1, vector<vector<string>>& pairs2, vector<double>& rates2) {
        unordered_map<string, int> idx;
        int id = 0;
        auto add = [&](const string& s) { if (!idx.count(s)) idx[s] = id++; };
        for (auto& p : pairs1) add(p[0]), add(p[1]);
        for (auto& p : pairs2) add(p[0]), add(p[1]);
        int n = id;
        vector<vector<double>> g1(n, vector<double>(n, 0)), g2(n, vector<double>(n, 0));
        for (int i = 0; i < n; ++i) g1[i][i] = g2[i][i] = 1.0;
        for (int i = 0; i < pairs1.size(); ++i) {
            int u = idx[pairs1[i][0]], v = idx[pairs1[i][1]];
            g1[u][v] = max(g1[u][v], rates1[i]);
            g1[v][u] = max(g1[v][u], 1.0 / rates1[i]);
        }
        for (int i = 0; i < pairs2.size(); ++i) {
            int u = idx[pairs2[i][0]], v = idx[pairs2[i][1]];
            g2[u][v] = max(g2[u][v], rates2[i]);
            g2[v][u] = max(g2[v][u], 1.0 / rates2[i]);
        }
        for (int k = 0; k < n; ++k)
            for (int i = 0; i < n; ++i)
                for (int j = 0; j < n; ++j) {
                    g1[i][j] = max(g1[i][j], g1[i][k] * g1[k][j]);
                    g2[i][j] = max(g2[i][j], g2[i][k] * g2[k][j]);
                }
        int start = idx[initialCurrency];
        double ans = 1.0;
        for (int i = 0; i < n; ++i) {
            double amt = 1.0 * g1[start][i] * g2[i][start];
            ans = max(ans, amt);
        }
        return ans;
    }
};

 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41


func maximizeAmount(initialCurrency string, pairs1 [][]string, rates1 []float64, pairs2 [][]string, rates2 []float64) float64 {
    idx := map[string]int{}
    id := 0
    add := func(s string) { if _, ok := idx[s]; !ok { idx[s] = id; id++ } }
    for _, p := range pairs1 { add(p[0]); add(p[1]) }
    for _, p := range pairs2 { add(p[0]); add(p[1]) }
    n := id
    g1 := make([][]float64, n)
    g2 := make([][]float64, n)
    for i := 0; i < n; i++ {
        g1[i] = make([]float64, n)
        g2[i] = make([]float64, n)
        g1[i][i] = 1.0
        g2[i][i] = 1.0
    }
    for i, p := range pairs1 {
        u, v := idx[p[0]], idx[p[1]]
        if rates1[i] > g1[u][v] { g1[u][v] = rates1[i] }
        if 1.0/rates1[i] > g1[v][u] { g1[v][u] = 1.0 / rates1[i] }
    }
    for i, p := range pairs2 {
        u, v := idx[p[0]], idx[p[1]]
        if rates2[i] > g2[u][v] { g2[u][v] = rates2[i] }
        if 1.0/rates2[i] > g2[v][u] { g2[v][u] = 1.0 / rates2[i] }
    }
    for k := 0; k < n; k++ {
        for i := 0; i < n; i++ {
            for j := 0; j < n; j++ {
                if g1[i][k]*g1[k][j] > g1[i][j] { g1[i][j] = g1[i][k] * g1[k][j] }
                if g2[i][k]*g2[k][j] > g2[i][j] { g2[i][j] = g2[i][k] * g2[k][j] }
            }
        }
    }
    start := idx[initialCurrency]
    ans := 1.0
    for i := 0; i < n; i++ {
        amt := g1[start][i] * g2[i][start]
        if amt > ans { ans = amt }
    }
    return ans
}

 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
27
28
29
30
31
32
33
34
35


class Solution {
    public double maximizeAmount(String initialCurrency, String[][] pairs1, double[] rates1, String[][] pairs2, double[] rates2) {
        Map<String, Integer> idx = new HashMap<>();
        int id = 0;
        for (String[] p : pairs1) { if (!idx.containsKey(p[0])) idx.put(p[0], id++); if (!idx.containsKey(p[1])) idx.put(p[1], id++); }
        for (String[] p : pairs2) { if (!idx.containsKey(p[0])) idx.put(p[0], id++); if (!idx.containsKey(p[1])) idx.put(p[1], id++); }
        int n = id;
        double[][] g1 = new double[n][n], g2 = new double[n][n];
        for (int i = 0; i < n; i++) Arrays.fill(g1[i], 0); for (int i = 0; i < n; i++) Arrays.fill(g2[i], 0);
        for (int i = 0; i < n; i++) g1[i][i] = g2[i][i] = 1.0;
        for (int i = 0; i < pairs1.length; i++) {
            int u = idx.get(pairs1[i][0]), v = idx.get(pairs1[i][1]);
            g1[u][v] = Math.max(g1[u][v], rates1[i]);
            g1[v][u] = Math.max(g1[v][u], 1.0 / rates1[i]);
        }
        for (int i = 0; i < pairs2.length; i++) {
            int u = idx.get(pairs2[i][0]), v = idx.get(pairs2[i][1]);
            g2[u][v] = Math.max(g2[u][v], rates2[i]);
            g2[v][u] = Math.max(g2[v][u], 1.0 / rates2[i]);
        }
        for (int k = 0; k < n; k++)
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++) {
                    g1[i][j] = Math.max(g1[i][j], g1[i][k] * g1[k][j]);
                    g2[i][j] = Math.max(g2[i][j], g2[i][k] * g2[k][j]);
                }
        int start = idx.get(initialCurrency);
        double ans = 1.0;
        for (int i = 0; i < n; i++) {
            double amt = g1[start][i] * g2[i][start];
            ans = Math.max(ans, amt);
        }
        return ans;
    }
}

 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
27
28
29
30
31
32
33
34
35
36


class Solution {
    fun maximizeAmount(initialCurrency: String, pairs1: Array<Array<String>>, rates1: DoubleArray, pairs2: Array<Array<String>>, rates2: DoubleArray): Double {
        val idx = mutableMapOf<String, Int>()
        var id = 0
        fun add(s: String) { if (s !in idx) { idx[s] = id++; } }
        for (p in pairs1) { add(p[0]); add(p[1]) }
        for (p in pairs2) { add(p[0]); add(p[1]) }
        val n = id
        val g1 = Array(n) { DoubleArray(n) { 0.0 } }
        val g2 = Array(n) { DoubleArray(n) { 0.0 } }
        for (i in 0 until n) { g1[i][i] = 1.0; g2[i][i] = 1.0 }
        for (i in pairs1.indices) {
            val u = idx[pairs1[i][0]]!!; val v = idx[pairs1[i][1]]!!
            g1[u][v] = maxOf(g1[u][v], rates1[i])
            g1[v][u] = maxOf(g1[v][u], 1.0 / rates1[i])
        }
        for (i in pairs2.indices) {
            val u = idx[pairs2[i][0]]!!; val v = idx[pairs2[i][1]]!!
            g2[u][v] = maxOf(g2[u][v], rates2[i])
            g2[v][u] = maxOf(g2[v][u], 1.0 / rates2[i])
        }
        for (k in 0 until n)
            for (i in 0 until n)
                for (j in 0 until n) {
                    g1[i][j] = maxOf(g1[i][j], g1[i][k] * g1[k][j])
                    g2[i][j] = maxOf(g2[i][j], g2[i][k] * g2[k][j])
                }
        val start = idx[initialCurrency]!!
        var ans = 1.0
        for (i in 0 until n) {
            val amt = g1[start][i] * g2[i][start]
            ans = maxOf(ans, amt)
        }
        return ans
    }
}

 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
27
28
29
30
31
32
33
34
35
36
37


class Solution:
    def maximizeAmount(self, initialCurrency: str, pairs1: list[list[str]], rates1: list[float], pairs2: list[list[str]], rates2: list[float]) -> float:
        idx = {}
        id = 0
        def add(s):
            nonlocal id
            if s not in idx:
                idx[s] = id
                id += 1
        for p in pairs1:
            add(p[0]); add(p[1])
        for p in pairs2:
            add(p[0]); add(p[1])
        n = id
        g1 = [[0.0]*n for _ in range(n)]
        g2 = [[0.0]*n for _ in range(n)]
        for i in range(n):
            g1[i][i] = g2[i][i] = 1.0
        for i, (a, b) in enumerate(pairs1):
            u, v = idx[a], idx[b]
            g1[u][v] = max(g1[u][v], rates1[i])
            g1[v][u] = max(g1[v][u], 1.0 / rates1[i])
        for i, (a, b) in enumerate(pairs2):
            u, v = idx[a], idx[b]
            g2[u][v] = max(g2[u][v], rates2[i])
            g2[v][u] = max(g2[v][u], 1.0 / rates2[i])
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    g1[i][j] = max(g1[i][j], g1[i][k] * g1[k][j])
                    g2[i][j] = max(g2[i][j], g2[i][k] * g2[k][j])
        start = idx[initialCurrency]
        ans = 1.0
        for i in range(n):
            amt = g1[start][i] * g2[i][start]
            ans = max(ans, amt)
        return ans

 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
27
28
29
30
31
32
33
34
35
36
37
38
39


impl Solution {
    pub fn maximize_amount(initial_currency: String, pairs1: Vec<Vec<String>>, rates1: Vec<f64>, pairs2: Vec<Vec<String>>, rates2: Vec<f64>) -> f64 {
        use std::collections::HashMap;
        let mut idx = HashMap::new();
        let mut id = 0;
        let mut add = |s: &String| { if !idx.contains_key(s) { idx.insert(s.clone(), id); id += 1; } };
        for p in &pairs1 { add(&p[0]); add(&p[1]); }
        for p in &pairs2 { add(&p[0]); add(&p[1]); }
        let n = id;
        let mut g1 = vec![vec![0.0; n]; n];
        let mut g2 = vec![vec![0.0; n]; n];
        for i in 0..n { g1[i][i] = 1.0; g2[i][i] = 1.0; }
        for (i, p) in pairs1.iter().enumerate() {
            let u = idx[&p[0]]; let v = idx[&p[1]];
            g1[u][v] = g1[u][v].max(rates1[i]);
            g1[v][u] = g1[v][u].max(1.0 / rates1[i]);
        }
        for (i, p) in pairs2.iter().enumerate() {
            let u = idx[&p[0]]; let v = idx[&p[1]];
            g2[u][v] = g2[u][v].max(rates2[i]);
            g2[v][u] = g2[v][u].max(1.0 / rates2[i]);
        }
        for k in 0..n {
            for i in 0..n {
                for j in 0..n {
                    g1[i][j] = g1[i][j].max(g1[i][k] * g1[k][j]);
                    g2[i][j] = g2[i][j].max(g2[i][k] * g2[k][j]);
                }
            }
        }
        let start = idx[&initial_currency];
        let mut ans = 1.0;
        for i in 0..n {
            let amt = g1[start][i] * g2[i][start];
            if amt > ans { ans = amt; }
        }
        ans
    }
}

 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
27
28
29
30
31
32
33
34
35
36


class Solution {
    maximizeAmount(initialCurrency: string, pairs1: string[][], rates1: number[], pairs2: string[][], rates2: number[]): number {
        const idx = new Map<string, number>();
        let id = 0;
        const add = (s: string) => { if (!idx.has(s)) idx.set(s, id++); };
        for (const p of pairs1) { add(p[0]); add(p[1]); }
        for (const p of pairs2) { add(p[0]); add(p[1]); }
        const n = id;
        const g1 = Array.from({length: n}, () => Array(n).fill(0));
        const g2 = Array.from({length: n}, () => Array(n).fill(0));
        for (let i = 0; i < n; i++) g1[i][i] = g2[i][i] = 1.0;
        for (let i = 0; i < pairs1.length; i++) {
            const u = idx.get(pairs1[i][0])!, v = idx.get(pairs1[i][1])!;
            g1[u][v] = Math.max(g1[u][v], rates1[i]);
            g1[v][u] = Math.max(g1[v][u], 1.0 / rates1[i]);
        }
        for (let i = 0; i < pairs2.length; i++) {
            const u = idx.get(pairs2[i][0])!, v = idx.get(pairs2[i][1])!;
            g2[u][v] = Math.max(g2[u][v], rates2[i]);
            g2[v][u] = Math.max(g2[v][u], 1.0 / rates2[i]);
        }
        for (let k = 0; k < n; k++)
            for (let i = 0; i < n; i++)
                for (let j = 0; j < n; j++) {
                    g1[i][j] = Math.max(g1[i][j], g1[i][k] * g1[k][j]);
                    g2[i][j] = Math.max(g2[i][j], g2[i][k] * g2[k][j]);
                }
        const start = idx.get(initialCurrency)!;
        let ans = 1.0;
        for (let i = 0; i < n; i++) {
            const amt = g1[start][i] * g2[i][start];
            ans = Math.max(ans, amt);
        }
        return ans;
    }
}

Complexity

⏰ Time complexity: O(n^3), where n is the number of currencies, due to the Floyd-Warshall algorithm.
🧺 Space complexity: O(n^2), for storing the conversion graphs.

Problem#

Example 1#

Example 2#

Example 3#

Constraints#

Examples#

Solution#

Method 1 – Graph Traversal (Floyd-Warshall for All-Pairs Max Product)#

Intuition#

Approach#

Code#

Complexity#