Problem Description

You start with 1.0 unit of a currency called initialCurrency. You have two days to perform currency exchanges to maximize the amount of initialCurrency you end up with.

For each day, you're given:

• Day 1: Arrays pairs1 and rates1
• Day 2: Arrays pairs2 and rates2

Each pair pairs[i] = [startCurrency, targetCurrency] with corresponding rates[i] means you can convert from startCurrency to targetCurrency at the given rate. Additionally, you can always convert backwards from targetCurrency to startCurrency at rate 1/rate.

The rules are:

1. On Day 1, you can perform any number of currency conversions (including zero) using only the Day 1 rates
2. On Day 2, you can perform any number of currency conversions (including zero) using only the Day 2 rates
3. Day 2 conversions must come after Day 1 conversions

Your goal is to find the maximum amount of initialCurrency you can have after both days.

For example, if you start with currency "A":

• On Day 1, you might convert A → B → C to end up with some amount of currency C
• On Day 2, you might convert C → D → A to convert back to the initial currency A
• The final answer would be the maximum amount of A you can obtain through any sequence of valid conversions

The solution uses graph traversal (DFS) to:

1. Build a graph of all possible conversions and compute the maximum amount of each currency reachable from initialCurrency on Day 1
2. Build another graph for Day 2 to find all possible paths back to initialCurrency
3. Find the maximum by trying all intermediate currencies - the amount you can have of currency X after Day 1, divided by the rate needed to convert from initialCurrency to X on Day 2 (which gives you the amount of initialCurrency you'd get back)

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The problem involves currencies as nodes and exchange rates as weighted edges between them. Each currency pair represents a bidirectional edge in the graph.

Is it a tree?

• No: The currency exchange network is not a tree - it can have cycles (e.g., USD → EUR → GBP → USD) and multiple paths between currencies.

Is the problem related to directed acyclic graphs?

• No: The graph has cycles since you can convert currencies back and forth (each conversion has a reverse conversion at rate 1/r).

Is the problem related to shortest paths?

• No: We're looking for the maximum amount achievable, not shortest paths. We want to explore all reachable currencies and track the maximum amount we can have of each currency.

Does the problem involve connectivity?

• Yes: We need to find all currencies reachable from the initial currency on Day 1, and then determine which of those can be converted back to the initial currency on Day 2.

Does the problem have small constraints?

• Yes: Currency exchange problems typically have manageable constraints (limited number of currencies and exchange pairs).

DFS/backtracking?

• Yes: DFS is ideal here to traverse the graph and compute the maximum amount of each currency reachable from the initial currency.

Conclusion: The flowchart suggests using DFS to explore the currency exchange graph. The solution uses DFS twice:

1. First DFS on Day 1's graph to find the maximum amount of each currency reachable from initialCurrency
2. Second DFS on Day 2's graph to find conversion rates back to initialCurrency
3. The answer is the maximum value obtained by trying all intermediate currencies as transition points between the two days

Intuition

The key insight is to think of this problem as finding the best "intermediate currency" to hold between Day 1 and Day 2.

Since we must perform Day 1 operations before Day 2 operations, we can break this into two independent subproblems:

1. What's the maximum amount of each currency we can obtain starting from initialCurrency on Day 1?
2. How can we convert from each currency back to initialCurrency on Day 2?

Imagine you start with 1.0 unit of currency A. After Day 1, you might have converted it to some other currency X with amount amount_X. Then on Day 2, you need to convert X back to A. The final amount of A you get is amount_X * rate(X→A on Day 2).

But here's the trick: if we can reach X from A on Day 2 with some rate r, then we can go from X back to A with rate 1/r. So if d2[X] represents the maximum amount of X we can get starting from 1.0 unit of A on Day 2, then converting from X back to A gives us amount_X / d2[X] units of A.

This leads to our strategy:

1. Use DFS from initialCurrency on Day 1's graph to find the maximum amount of every reachable currency
2. Use DFS from initialCurrency on Day 2's graph to find conversion rates from initialCurrency to all reachable currencies
3. Try every possible intermediate currency X: calculate d1[X] / d2[X] (amount after Day 1 divided by the rate to reach X from initial on Day 2)
4. Return the maximum value found

The DFS is perfect here because:

• We need to explore all paths to find maximum amounts (not just shortest paths)
• The graph might have cycles, but DFS with visited tracking handles this
• We're essentially computing the "reachability with maximum value" from a source node

The beauty of this approach is that it avoids the complexity of trying all possible conversion sequences by recognizing that we only need to consider which currency to "pause" at between the two days.

Learn more about Depth-First Search, Breadth-First Search and Graph patterns.

Solution Approach

The solution implements the two-phase DFS strategy we identified. Let's walk through the implementation:

Main Function (maxAmount):

1. Build two dictionaries d1 and d2 that store the maximum amount of each currency reachable from initialCurrency on Day 1 and Day 2 respectively
2. For each currency in d2, calculate the maximum amount of initialCurrency obtainable by using that currency as the intermediate: d1.get(a, 0) / r2
3. Return the maximum value found

Building the Graph (build function):

The build function constructs an adjacency list representation of the currency graph and performs DFS:

1. Graph Construction:

   g = defaultdict(list)
   for (a, b), r in zip(pairs, rates):
       g[a].append((b, r))      # Forward edge with rate r
       g[b].append((a, 1 / r))  # Reverse edge with rate 1/r

   Each currency pair creates two directed edges - one for each direction of conversion.

2. DFS Traversal:

   def dfs(a: str, v: float):
       d[a] = v                 # Store max amount of currency a
       for b, r in g[a]:        # Explore neighbors
           if b not in d:       # Avoid revisiting
               dfs(b, v * r)    # Multiply current amount by rate

   • Start from init currency with amount 1.0
   • For each unvisited neighbor, multiply the current amount by the exchange rate
   • The visited check (if b not in d) prevents infinite loops in cyclic graphs

Final Calculation:

The expression max(d1.get(a, 0) / r2 for a, r2 in d2.items()) computes:

• For each currency a reachable on Day 2 with amount r2 from initial
• d1.get(a, 0) gives the amount of currency a after Day 1 (0 if not reachable)
• d1.get(a, 0) / r2 converts back to initial currency: if we have X units of currency a and it takes r2 units of initial to get 1 unit of a on Day 2, then we can convert X units of a back to X/r2 units of initial

Time Complexity: O(V + E) for each DFS where V is the number of unique currencies and E is the number of exchange pairs. Since we run DFS twice, total is O(V + E).

Space Complexity: O(V + E) for storing the graph and the distance dictionaries.

Example Walkthrough

Let's walk through a concrete example to understand the solution approach.

Given:

• initialCurrency = "USD"
• Day 1: pairs1 = [["USD", "EUR"], ["EUR", "GBP"]], rates1 = [2.0, 3.0]
• Day 2: pairs2 = [["GBP", "USD"], ["EUR", "USD"]], rates2 = [5.0, 4.0]

Step 1: Build Day 1 Graph and Find Maximum Amounts

First, we build the graph for Day 1:

• USD → EUR at rate 2.0 (and EUR → USD at rate 0.5)
• EUR → GBP at rate 3.0 (and GBP → EUR at rate 0.333...)

Starting DFS from USD with 1.0:

• Visit USD: d1["USD"] = 1.0
• Explore USD → EUR: d1["EUR"] = 1.0 × 2.0 = 2.0
• From EUR, explore EUR → GBP: d1["GBP"] = 2.0 × 3.0 = 6.0
• EUR → USD is not explored (USD already visited)

Result: d1 = {"USD": 1.0, "EUR": 2.0, "GBP": 6.0}

This means after Day 1:

• We can have 1.0 USD (do nothing)
• We can have 2.0 EUR (convert USD → EUR)
• We can have 6.0 GBP (convert USD → EUR → GBP)

Step 2: Build Day 2 Graph and Find Conversion Rates from Initial Currency

Build the graph for Day 2:

• GBP → USD at rate 5.0 (and USD → GBP at rate 0.2)
• EUR → USD at rate 4.0 (and USD → EUR at rate 0.25)

Starting DFS from USD with 1.0:

• Visit USD: d2["USD"] = 1.0
• Explore USD → GBP: d2["GBP"] = 1.0 × 0.2 = 0.2
• Explore USD → EUR: d2["EUR"] = 1.0 × 0.25 = 0.25

Result: d2 = {"USD": 1.0, "GBP": 0.2, "EUR": 0.25}

This means on Day 2, starting with 1.0 USD:

• To get 1 GBP, we need 5 USD (so d2["GBP"] = 0.2, meaning 1 USD gives 0.2 GBP)
• To get 1 EUR, we need 4 USD (so d2["EUR"] = 0.25, meaning 1 USD gives 0.25 EUR)

Step 3: Calculate Maximum for Each Intermediate Currency

Now we try each currency as an intermediate holding between days:

1. Hold USD between days:
   • After Day 1: 1.0 USD
   • Converting back on Day 2: 1.0 / 1.0 = 1.0 USD
2. Hold EUR between days:
   • After Day 1: 2.0 EUR
   • Converting back on Day 2: 2.0 / 0.25 = 8.0 USD
   • (Since 0.25 EUR costs 1 USD on Day 2, 2.0 EUR can be sold for 8.0 USD)
3. Hold GBP between days:
   • After Day 1: 6.0 GBP
   • Converting back on Day 2: 6.0 / 0.2 = 30.0 USD
   • (Since 0.2 GBP costs 1 USD on Day 2, 6.0 GBP can be sold for 30.0 USD)

Step 4: Return Maximum

The maximum is 30.0 USD, achieved by:

• Day 1: Convert USD → EUR → GBP (1.0 → 2.0 → 6.0)
• Hold 6.0 GBP overnight
• Day 2: Convert GBP → USD at rate 5.0 (6.0 × 5.0 = 30.0)

The key insight is that d1[currency] / d2[currency] gives us the final amount of initial currency when using that currency as the intermediate holding.

Solution Implementation

Time and Space Complexity

Time Complexity: O(V + E)

The algorithm consists of two main phases, each building a graph and performing DFS traversal:

1. Building graph g in the build function: O(E) where E is the number of exchange pairs, as we iterate through all pairs once and add bidirectional edges.

2. DFS traversal in the build function: O(V + E) where V is the number of unique currencies and E is the number of edges. Each vertex is visited once (tracked by dictionary d), and we explore all edges from visited vertices.

3. The build function is called twice - once for pairs1/rates1 and once for pairs2/rates2. If we denote V1, E1 for the first day and V2, E2 for the second day, this gives us O(V1 + E1) + O(V2 + E2).

4. The final max computation iterates through all currencies in d2, which is O(V2).

Overall time complexity: O(V1 + E1 + V2 + E2) which simplifies to O(V + E) where V represents total unique currencies and E represents total exchange pairs across both days.

Space Complexity: O(V + E)

1. Graph g in each build call: O(V + E) - stores adjacency list with all vertices and bidirectional edges.

2. Dictionary d in each build call: O(V) - stores exchange rate for each reachable currency.

3. DFS recursion stack: O(V) in worst case when the graph forms a chain.

4. Since build is called twice, we have space usage of O(V1 + E1) and O(V2 + E2).

Overall space complexity: O(V + E) where V is the total number of unique currencies and E is the total number of exchange pairs.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Cycles and Infinite Loops in Currency Exchange

The Problem: The most critical pitfall in this solution is not properly handling cycles in the currency exchange graph. Without the visited check (if next_currency not in exchange_rates), the DFS would enter infinite loops when encountering cycles like A → B → C → A.

Why It Happens: Currency exchange graphs often contain cycles since currencies can typically be exchanged bidirectionally. Additionally, longer cycles through multiple currencies are common in real exchange systems.

The Solution: The code correctly prevents this by tracking visited currencies in the exchange_rates dictionary. Once a currency is visited, it won't be explored again:

if next_currency not in exchange_rates:  # Critical check
    next_value = current_value * exchange_rate
    depth_first_search(next_currency, next_value)

Pitfall 2: Missing Optimal Paths Due to Early Termination

The Problem: The DFS visits each currency only once and records the first path's exchange rate. However, in a graph with cycles, there might be multiple paths to the same currency with different rates. The current implementation might miss the optimal rate if a suboptimal path is found first.

Example Scenario:

• Path 1: A → B (rate: 2.0)
• Path 2: A → C → B (rate: 3.0) If DFS explores Path 1 first, it records B with rate 2.0 and never updates it, missing the better rate of 3.0.

The Solution: For maximum exchange rates, modify the DFS to use dynamic programming or Bellman-Ford-like relaxation:

def depth_first_search(current_currency: str, current_value: float) -> None:
    # Only update if we found a better rate
    if current_currency not in exchange_rates or current_value > exchange_rates[current_currency]:
        exchange_rates[current_currency] = current_value
      
        # Continue exploring from this currency
        for next_currency, exchange_rate in adjacency_graph[current_currency]:
            next_value = current_value * exchange_rate
            # Only explore if potentially better
            if next_currency not in exchange_rates or next_value > exchange_rates[next_currency]:
                depth_first_search(next_currency, next_value)

Pitfall 3: Handling Edge Cases

The Problem: The solution doesn't explicitly handle several edge cases:

1. When initialCurrency doesn't exist in either day's pairs
2. When there's no path back to initialCurrency on Day 2
3. Empty pairs/rates arrays

The Solution: Add explicit handling for these cases:

def maxAmount(self, initialCurrency: str, pairs1: List[List[str]], 
             rates1: List[float], pairs2: List[List[str]], rates2: List[float]) -> float:
    # Handle empty inputs
    if not pairs1 or not pairs2:
        return 1.0  # No exchanges possible, return initial amount
  
    market1_rates = self._build_exchange_rates(pairs1, rates1, initialCurrency)
    market2_rates = self._build_exchange_rates(pairs2, rates2, initialCurrency)
  
    # If initial currency not reachable in market2, can't convert back
    if initialCurrency not in market2_rates:
        return 1.0
  
    # Start with the option of no exchanges (keeping initial currency)
    max_amount = 1.0
  
    for currency, rate_from_initial in market2_rates.items():
        if currency in market1_rates:
            round_trip_value = market1_rates[currency] / rate_from_initial
            max_amount = max(max_amount, round_trip_value)
  
    return max_amount

Pitfall 4: Floating Point Precision Issues

The Problem: Multiple currency conversions can accumulate floating-point errors, especially with many exchanges or extreme rates.

The Solution: While not always necessary for interview problems, consider using decimal arithmetic for financial calculations or setting a reasonable precision threshold when comparing values.