Skip to main content
Talentd

Maximize Amount After Two Days of Conversions - Solution & Explanation

MediumArrayStringDepth-First SearchBreadth-First Search8 min readAsked at: Uber, Google, Rippling
Practice this problem

Problem Statement

You are given a string initialCurrency, and you start with 1.0 of initialCurrency.

You are also given four arrays with currency pairs (strings) and rates (real numbers):

  • pairs1[i] = [startCurrencyi, targetCurrencyi] denotes that you can convert from startCurrencyi to targetCurrencyi at a rate of rates1[i] on day 1.
  • pairs2[i] = [startCurrencyi, targetCurrencyi] denotes that you can convert from startCurrencyi to targetCurrencyi at a rate of rates2[i] on day 2.
  • Also, each targetCurrency can be converted back to its corresponding startCurrency at a rate of 1 / rate.

You can perform any number of conversions, including zero, using rates1 on day 1, followed by any number of additional conversions, including zero, using rates2 on day 2.

Return the maximum amount of initialCurrency you can have after performing any number of conversions on both days in order.

Note: Conversion rates are valid, and there will be no contradictions in the rates for either day. The rates for the days are independent of each other.

 

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

Explanation:

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

  • On Day 1:
    • Convert EUR to USD to get 2.0 USD.
    • Convert USD to JPY to get 6.0 JPY.
  • On Day 2:
    • Convert JPY to USD to get 24.0 USD.
    • Convert USD to CHF to get 120.0 CHF.
    • Finally, convert CHF to EUR to get 720.0 EUR.

Example 2:

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

Output: 1.50000

Explanation:

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

Explanation:

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.

Approach Overview

Problem Overview: You start with 1 unit of an initial currency. Day 1 and Day 2 each provide a set of currency conversion pairs with exchange rates. You may perform multiple conversions per day. The goal is to end with the maximum possible amount of the initial currency after completing conversions across both days.

Approach 1: Brute Force Conversion Exploration (Exponential Time)

A naive strategy explores every possible sequence of conversions on Day 1, then repeats the same exploration for Day 2. Each conversion multiplies the current amount by the exchange rate. Because currencies can connect in many ways, the number of possible paths grows exponentially. This approach models the problem as a graph and recursively tries all paths without pruning. Time complexity becomes O(b^d) where b is the branching factor of conversions and d is path depth, with O(d) recursion space. It works only for extremely small inputs and mainly helps verify correctness.

Approach 2: Graph Traversal with DFS/BFS (O(V + E))

Treat each day's conversions as a weighted graph where nodes are currencies and edges store the conversion rate. Since converting A → B with rate r implies B → A with rate 1/r, both directions are added to the graph. First traverse the Day 1 graph starting from the initial currency and compute the maximum amount reachable for every currency. A Depth-First Search or Breadth-First Search propagates the best multiplicative value across edges while updating the maximum seen for each node.

Next evaluate Day 2. For every currency reachable after Day 1, run another traversal on the Day 2 graph to determine the maximum amount of the initial currency obtainable from that currency. Multiply the Day 1 amount by the best Day 2 conversion result and keep the global maximum. Because the graphs are small, each traversal runs in O(V + E) time with O(V) space for visited states.

This method works because currency conversions form a weighted graph where the objective is maximizing a product along paths. Tracking the best amount per currency prevents unnecessary revisits and keeps the search linear relative to the graph size.

Recommended for interviews: Interviewers expect the graph modeling approach with DFS or BFS. The brute force explanation shows you recognize the search space, but representing currencies as graph nodes and propagating the maximum product demonstrates stronger algorithmic thinking.

Solution

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Conversion PathsExponentialO(d)Only for conceptual understanding or extremely small graphs
Graph Traversal with DFS/BFSO(V + E)O(V)General case; efficiently explores conversion graphs for both days
Graph Traversal with MemoizationO(V + E)O(V)Useful when multiple currencies require repeated Day 2 searches

Video Solution

Leetcode 3387 | Maximize Amount After Two Days of Conversions | Weekly Contest 428 • Road To FAANG • 2,104 views views

Watch 3 more video solutions →

Frequently Asked Questions

Is Maximize Amount After Two Days of Conversions easy or hard?
Maximize Amount After Two Days of Conversions is classified as a Medium problem. The difficulty comes from recognizing that currency conversions form a weighted graph and that maximizing the product along paths requires graph traversal across two separate conversion stages.
Maximize Amount After Two Days of Conversions Python/Java solution
Python, Java, C++, Go, and TypeScript implementations typically build adjacency lists for both days and perform DFS or BFS to propagate the maximum conversion value. Each step multiplies the current amount by the edge rate and updates the best value for that currency.
How to solve Maximize Amount After Two Days of Conversions in O(n)?
Construct adjacency lists for the conversion pairs and run DFS or BFS from the initial currency to compute maximum reachable amounts after Day 1. For each reachable currency, perform another traversal on the Day 2 graph to determine the best conversion back to the starting currency. Because each traversal touches nodes and edges once, the solution effectively runs in O(V + E).
What is the best approach for Maximize Amount After Two Days of Conversions?
Model each day's conversions as a weighted graph and run DFS or BFS to propagate the maximum currency amount along edges. First compute the best amount reachable from the starting currency on Day 1. Then evaluate Day 2 conversions to return to the initial currency and maximize the final product. This graph traversal runs in O(V + E) time.
Is Maximize Amount After Two Days of Conversions asked at Google/Amazon/Meta?
Graph traversal and currency conversion problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants often test graph modeling, multiplicative weights, and path optimization. Understanding DFS or BFS on weighted graphs is the key skill evaluated.
What data structure is used in Maximize Amount After Two Days of Conversions?
The core data structure is an adjacency list representing a graph of currencies and conversion rates. Traversal uses either DFS with recursion or BFS with a queue while maintaining a map of the best amount achieved for each currency.
What is the time complexity of Maximize Amount After Two Days of Conversions?
The optimal graph traversal approach runs in O(V + E) time for each search, where V is the number of currencies and E is the number of conversion pairs. Since the graph sizes are small and traversals are limited to two days of conversions, the total complexity remains linear relative to the graph size with O(V) space.

Ready to solve this problem?

Practice Maximize Amount After Two Days of Conversions with our built-in code editor and test cases.

Practice on FleetCode
Previous

Evaluate Division