#3387

Medium

auto_awesomeGraph traversal with depth-first search

LeetCode Problem Workspace

Maximize Amount After Two Days of Conversions

Compute the maximum currency amount after two days using graph traversal and depth-first search for optimal conversions.

array string depth first search breadth first search graph

Problem Statement

You are given an initial currency represented as a string and start with 1.0 unit of this currency. Each day offers a set of possible conversion pairs with associated rates.

On day 1, you may perform any number of conversions using the first set of rates, followed by day 2 conversions using the second set. Compute the maximum amount of the initial currency achievable after applying these conversions, considering all valid sequences.

Examples

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

To get the maximum amount of EUR , starting with 1.0 EUR :

Example 2

Input: initialCurrency = "NGN", pairs1 = [["NGN","EUR"]] , rates1 = [9.0] , pairs2 = [["NGN","EUR"]] , rates2 = [6.0]

Output: 1.50000

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

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.

Solution Approach

Model the conversions as a directed graph

Represent each currency as a node and each conversion pair as a directed edge weighted by its rate. Build two separate graphs for day 1 and day 2, capturing all possible conversion paths for depth-first exploration.

Perform depth-first search for day 1 conversions

From the initialCurrency node, recursively explore all reachable currencies on day 1. Track the cumulative product of conversion rates to each reachable currency to determine the maximum achievable amount for each intermediate currency.

Combine day 1 and day 2 paths to maximize returns

For each intermediate currency reached after day 1, perform a DFS on day 2 starting from that currency. Multiply day 2 rates with the day 1 cumulative amounts and record the maximum final amount returned to initialCurrency. Choose the optimal intermediate currency for the overall maximum.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the number of currencies and conversion pairs for both days, roughly O(n*m) in the worst case due to DFS traversals. Space complexity is proportional to graph size and recursive call stack, O(n+m).

What Interviewers Usually Probe

Notice the problem requires exploring all possible intermediate currencies for two-step conversions.
Recognize that cycles are absent, but handling multiple paths is crucial to avoid underestimating the maximum.
Focus on depth-first search traversal as the core pattern to find maximal cumulative rates.

Common Pitfalls or Variants

Common pitfalls

Failing to consider all intermediate currencies can lead to suboptimal results.
Multiplying rates incorrectly across day 1 and day 2 conversions reduces the final amount.
Ignoring disconnected currencies or paths that return to initialCurrency may miss the maximum achievable value.

Follow-up variants

Extend to three or more days of conversions with additional graphs and sequential DFS traversals.
Optimize using memoization to store maximum amounts for intermediate currencies to avoid repeated DFS computations.
Allow bidirectional conversion rates explicitly to increase reachable paths and maximize returns.

FAQ

What is the main strategy to maximize amount after two days of conversions?

Use depth-first search on both day 1 and day 2 graphs, tracking the cumulative product of conversion rates to identify the highest possible return.

Can I skip conversions on one of the days?

Yes, the optimal path may involve zero conversions on either day if it leads to a higher final amount.

Why is DFS preferred over BFS for this problem?

DFS allows exhaustive exploration of all conversion sequences and cumulative rate multiplications efficiently, fitting the graph traversal pattern.

How does the initialCurrency affect the solution?

The initialCurrency serves as the start and final node. Maximum amounts are measured relative to returning to this currency after both days.

Are cycles in conversion graphs an issue?

No, the problem guarantees no cycles exist, so DFS does not require cycle detection, simplifying traversal logic.

terminal

Solution

Solution 1

#### Python3

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

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

Continue Practicing

#3493 properties graph #3607 power grid maintenance #2467 most profitable path in a tree