#3387

Maximize Amount After Two Days of Conversions

specialist · 715 · lc medium +30 · 61.3% accepted · 160 likes · top 61%

⚑ DFS / BFS: Connected Components & Reachability

Description

You start with 1.0 of initialCurrency.

You are given four arrays for currency conversions:

- pairs1[i] = [startCurrencyi, targetCurrencyi] allows converting at rate rates1[i] on day 1.

- pairs2[i] = [startCurrencyi, targetCurrencyi] allows converting at rate rates2[i] on day 2.

- Any target currency can also convert back to its source at 1 / rate.

Perform any number of conversions using rates1 on day 1 (including none), then any number using rates2 on day 2 (including none).

Return the maximum amount of initialCurrency achievable at the end.

Conversion rates are consistent; day-1 and day-2 rates are independent.

Code

1

2

3

class Solution:
    def maxAmount(self, initialCurrency: str, pairs1: List[List[str]], rates1: List[float], pairs2: List[List[str]], rates2: List[float]) -> float:

class Solution:
    def maxAmount(self, initialCurrency: str, pairs1: List[List[str]], rates1: List[float], pairs2: List[List[str]], rates2: List[float]) -> float: