3387. Maximize Amount After Two Days of Conversions
Asked at Rippling
Difficulty
Medium
Time
O(V + E)
Space
O(V + E)
Pattern
Array
Companies
1
Problem
You start with exactly 1.0 unit of a currency called initialCurrency. You are given two days of exchange rates.
On day 1 you may make any number of conversions (including none) using the rates in pairs1 / rates1. Then, on day 2, you may make any number of conversions (including none) using the rates in pairs2 / rates2. Each pair [a, b] with rate r means 1 unit of a becomes r units of b. You can also go the other way: 1 unit of b becomes 1/r units of a.
After both days, you want to hold as much initialCurrency as possible. Return that maximum amount. The two days are independent, and the rates never contradict each other, so each day's graph is consistent.
Two days, one goal
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
Examples
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]720.00000initialCurrency = "NGN", pairs1 = [["NGN","EUR"]], rates1 = [9.0], pairs2 = [["NGN","EUR"]], rates2 = [6.0]1.50000initialCurrency = "USD", pairs1 = [["USD","EUR"]], rates1 = [1.0], pairs2 = [["EUR","JPY"]], rates2 = [10.0]1.00000Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Rippling | Medium | View all Rippling questions → |
How to Think About It
Brute force: try every possible two-step conversion path and track the maximum result.
Model currencies as nodes and conversions as directed weighted edges where the weight is the exchange rate.
Use DFS or BFS from the source currency to find the best single-day conversion to any intermediate currency.
For each intermediate currency reachable on day one, perform a second BFS/DFS to the target on day two and multiply the rates.
Optimal: run two graph traversals — one from source and one reversed from target — then combine results in O(V + E) time.
Optimal Approach
Build a directed graph where each node is a currency and each edge stores the exchange rate. Perform a DFS or BFS from the source currency to compute the maximum amount reachable after one day for every intermediate currency. Then perform a second traversal from each intermediate currency (or equivalently a reversed BFS from the target) to find the best rate to the target. Multiply the day-one and day-two rates for each intermediate currency and take the maximum. This two-pass approach avoids enumerating all pairs and runs in O(V + E) time.
Best amount per currency, then combine
What Trips People Up in Real Interviews
Clarify whether cycles in the graph are allowed and whether you can revisit currencies across days.
Watch out for floating-point precision — compare using a small epsilon rather than exact equality.
Make sure you handle the case where no valid conversion path exists (return -1 or 0 as specified).
Discuss whether the graph is guaranteed to be connected and what the edge case of a single-node graph looks like.
Explain the time complexity clearly: two graph traversals give O(V + E) which is efficient for the constraints.
Solution Code
O(V + E) timefrom collections import defaultdict
def maxAmount(initialCurrency, pairs, rates):
graph = defaultdict(list)
for (a, b), r in zip(pairs, rates):
graph[a].append((b, r))
graph[b].append((a, 1.0 / r))
def bfs(start):
visited = {}
queue = [(start, 1.0)]
visited[start] = 1.0
while queue:
node, amt = queue.pop(0)
for nei, rate in graph[node]:
new_amt = amt * rate
if nei not in visited or new_amt > visited[nei]:
visited[nei] = new_amt
queue.append((nei, new_amt))
return visited
day1 = bfs(initialCurrency)
best = 0.0
for intermediate, amt1 in day1.items():
day2 = bfs(intermediate)
if initialCurrency in day2:
best = max(best, amt1 * day2[initialCurrency])
return bestFrequently Asked Questions
What is the Maximize Amount After Two Days of Conversions problem?
You are given a list of currency conversions represented as directed edges with exchange rates. Starting with a given amount of a source currency, you must perform conversions over at most two days, where each day you can convert along any path in the graph. The goal is to maximize the final amount of the target currency by choosing the optimal sequence of conversions.
How do you solve Maximize Amount After Two Days of Conversions?
The optimal approach runs in O(V + E) time and O(V + E) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Maximize Amount After Two Days of Conversions?
Maximize Amount After Two Days of Conversions is asked at Rippling. It is a medium difficulty problem.
What are common mistakes on Maximize Amount After Two Days of Conversions?
- Clarify whether cycles in the graph are allowed and whether you can revisit currencies across days.
- Watch out for floating-point precision — compare using a small epsilon rather than exact equality.
- Make sure you handle the case where no valid conversion path exists (return -1 or 0 as specified).
- Discuss whether the graph is guaranteed to be connected and what the edge case of a single-node graph looks like.
- Explain the time complexity clearly: two graph traversals give O(V + E) which is efficient for the constraints.