Problem Statement in English

You’re given an initial currency ini, two lists of currency pairs p1 and p2 with their corresponding exchange rates r1 and r2.

p1 and r1 represent the exchange rates for the first day, while p2 and r2 represent the exchange rates for the second day. Each pair in p1 and p2 consists of two currencies, and the corresponding rate in r1 and r2 indicates how much of the second currency you get for 1 unit of the first currency.

You can perform two conversions: one using the pairs in p1 and another using the pairs in p2. Your task is to find the maximum amount of the initial currency you can get after performing any number of day 1 conversions on day 1, then any number of day 2 conversions on day 2, starting with 1 unit of the initial currency ini, on day 1.

You can also convert back any curreny to its source currency at a rate of 1 / rate for any pair in p1 and p2.

Approach

Since there is a temportal boundary between the two sets of conversions, we can treat them as two separate graphs. We can solve problem for day 1, and then try every day 1 currency as a starting point for day 2.

We can perform a breadth-first search (BFS) on the first graph to find the maximum amount of each currency we can get starting from ini. Then, for each currency we can get from the first graph, we can perform another BFS on the second graph to find the maximum amount of ini we can get back.

And we’re done!

Solution in Python


class Solution:
    def maxAmount(self, ini: str, p1: List[List[str]], r1: List[float], p2: List[List[str]], r2: List[float]) -> float:
        g1 = defaultdict(list)
        g2 = defaultdict(list)
        
        for i in range(len(p1)):
            a, b = p1[i]
            rate = r1[i]
            g1[a].append((b, rate))
            g1[b].append((a, 1 / rate))
        
        for i in range(len(p2)):
            a, b = p2[i]
            rate = r2[i]
            g2[a].append((b, rate))
            g2[b].append((a, 1 / rate))
        
        def bfs(graph, start, amt):
            max_amt = defaultdict(float)
            max_amt[start] = amt
            q = deque([(start, amt)])
            
            while q:
                curr, amt = q.popleft()
                for nxt, rate in graph[curr]:
                    new_amt = amt * rate
                    if new_amt > max_amt[nxt]:
                        max_amt[nxt] = new_amt
                        q.append((nxt, new_amt))
            
            return max_amt
        
        res1 = bfs(g1, ini, 1.0)
        res2 = 0.0
        
        for curr, amt in res1.items():
            res2 = max(res2, bfs(g2, curr, amt)[ini])
        
        return res2

Complexity

  • Time: $O((V_1 * E_1) + (V_2 * E_2))$
    Since in graph 1, we visit each vertex and edge at most once, and the same applies for graph 2.

  • Space: $O(|p1| + |p2|)$
    As we store the graphs in adjacency list format, and the maximum amount for each currency.

Mistakes I Made

I overcomplicated the problem, and then had to look it up :)

And we are done.