LeetCode Problem 3387

Difficulty: 🟡 Medium
Topics: Array, String, Depth-First Search, Breadth-First Search, Graph Theory

Solution

LeetCode 3387 - Maximize Amount After Two Days of Conversions

Problem Understanding

This problem models currency conversions as graph traversal across two separate days. You begin with exactly 1.0 unit of initialCurrency, and you may perform any number of exchanges on day 1 using the first set of conversion rates, followed by any number of exchanges on day 2 using the second set of conversion rates.

Each conversion pair defines a bidirectional exchange relationship. If you can convert currency A to currency B at rate r, then you can also convert B back to A at rate 1 / r. This means every input pair creates two directed edges in a graph.

The key requirement is that after completing both days of conversions, you want to maximize the amount of the original currency you end up with. The order matters significantly:

1. You may perform arbitrary conversions using only day 1 rates.
2. After day 1 finishes, you may perform arbitrary conversions using only day 2 rates.
3. The final currency must again be initialCurrency.

The input size is very small. Each day contains at most 10 currency pairs, which means the total graph size is tiny. This tells us that exhaustive graph traversal is feasible. The challenge is not scale, but correctly combining the two independent conversion systems.

An important observation is that the conversion graphs are guaranteed to have no contradictions or arbitrage cycles within a single day. This means every currency has a unique implied exchange rate relative to every connected currency on that day. Because of this property, simple graph traversal is sufficient and we do not need Bellman-Ford or arbitrage detection algorithms.

Several edge cases are important:

• It may be optimal to perform zero conversions on one or both days.
• Some currencies may only exist in one day's graph.
• The best strategy may involve converting away from the initial currency on day 1 and converting back on day 2.
• Exchange rates can involve floating point multiplication chains, so precision handling matters.
• The graph may be disconnected, meaning some currencies are unreachable.

Approaches

Brute Force Approach

A brute force strategy would try every possible sequence of conversions on day 1, then every possible sequence on day 2, while tracking the resulting amounts.

This works because the graphs are small, but it quickly becomes impractical conceptually. Even though the graphs are tiny, the number of possible paths grows exponentially if cycles and repeated traversals are considered. Since conversions are reversible, naive DFS without careful pruning could repeatedly revisit currencies and generate enormous recursion trees.

The brute force method is also inefficient because it recomputes the same conversion relationships many times. For example, the conversion rate from EUR to JPY on day 1 does not depend on the path exploration order. Once computed, it should be reused.

Key Insight

The crucial observation is that each day's graph defines a fixed exchange ratio between any two connected currencies.

Suppose on day 1 we determine:

• How much of every currency we can obtain starting from initialCurrency.

Then on day 2 we determine:

• How much initialCurrency we can obtain starting from every currency.

If we combine these two pieces of information, then for every intermediate currency C:

(day1 amount of C) × (day2 conversion from C back to initialCurrency)

gives the final achievable amount.

This transforms the problem into two independent graph traversals.

Because each graph has no contradictory cycles, a simple DFS or BFS can compute all reachable exchange rates from a starting currency.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	O(path length)	Explores all conversion sequences
Optimal	O(V + E)	O(V + E)	Two graph traversals with cached rates

Since the graph size is tiny, the practical runtime is extremely fast.

Algorithm Walkthrough

1. Construct two bidirectional graphs, one for each day.

Each currency becomes a node. For every pair [u, v] with rate r:

• Add edge u -> v with weight r
• Add edge v -> u with weight 1 / r

This allows traversal in both directions. 2. Traverse the day 1 graph starting from initialCurrency.

During DFS, maintain the current accumulated conversion amount.

For example:

• Starting at EUR with amount 1.0
• Moving along edge with rate 2.0 gives 2.0
• Moving again with rate 3.0 gives 6.0

Store the maximum obtainable amount for every reachable currency. 3. Traverse the day 2 graph starting from initialCurrency.

This step computes how much of each currency corresponds to one unit of initialCurrency on day 2.

Instead of thinking forward, interpret the traversal as computing conversion relationships relative to the initial currency. 4. For every currency reachable on day 1:

• Let amount1[currency] be how much of that currency we can obtain after day 1.
• Let amount2[currency] represent the conversion factor between that currency and the initial currency on day 2.

The final obtainable amount is:

amount1[currency] / amount2[currency]

because amount2[currency] tells us how many units of that currency equal one unit of the initial currency. 5. Track the maximum result across all currencies. 6. Return the best value found.

Why it works

Each graph defines a unique multiplicative exchange relationship between connected currencies. The DFS traversal computes these relationships exactly by multiplying edge weights along paths.

For any intermediate currency C:

• Day 1 computes how much C we can obtain from one unit of the initial currency.
• Day 2 computes the inverse relationship between C and the initial currency.

Multiplying these compatible exchange ratios yields the exact final amount obtainable after both days.

Because every possible reachable currency is evaluated as an intermediate state, the algorithm considers every valid strategy.

Python Solution

from collections import defaultdict
from typing import List, Dict

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

        def build_graph(pairs: List[List[str]], rates: List[float]):
            graph = defaultdict(list)

            for (u, v), rate in zip(pairs, rates):
                graph[u].append((v, rate))
                graph[v].append((u, 1.0 / rate))

            return graph

        def dfs(
            graph: Dict[str, List[tuple]],
            currency: str,
            amount: float,
            values: Dict[str, float]
        ):
            values[currency] = amount

            for neighbor, rate in graph[currency]:
                if neighbor not in values:
                    dfs(graph, neighbor, amount * rate, values)

        graph1 = build_graph(pairs1, rates1)
        graph2 = build_graph(pairs2, rates2)

        day1_values = {}
        dfs(graph1, initialCurrency, 1.0, day1_values)

        day2_values = {}
        dfs(graph2, initialCurrency, 1.0, day2_values)

        answer = 1.0

        for currency, amount in day1_values.items():
            if currency in day2_values:
                final_amount = amount / day2_values[currency]
                answer = max(answer, final_amount)

        return answer

The implementation begins by building adjacency lists for both days. Each conversion pair creates two directed edges, one using the given rate and one using its reciprocal.

The DFS function computes multiplicative conversion values relative to the starting currency. The values dictionary stores the computed amount for every reachable currency.

After constructing both graphs, we run DFS twice:

• Once on day 1
• Once on day 2

The first traversal determines how much of each currency can be obtained after day 1. The second traversal determines the relative value of currencies with respect to the initial currency during day 2.

Finally, we iterate through all currencies reachable on day 1. If a currency is also reachable on day 2, we compute the final achievable amount and update the answer.

Go Solution

package main

type Edge struct {
	to   string
	rate float64
}

func maxAmount(
	initialCurrency string,
	pairs1 [][]string,
	rates1 []float64,
	pairs2 [][]string,
	rates2 []float64,
) float64 {

	buildGraph := func(pairs [][]string, rates []float64) map[string][]Edge {
		graph := make(map[string][]Edge)

		for i, pair := range pairs {
			u := pair[0]
			v := pair[1]
			rate := rates[i]

			graph[u] = append(graph[u], Edge{v, rate})
			graph[v] = append(graph[v], Edge{u, 1.0 / rate})
		}

		return graph
	}

	var dfs func(
		graph map[string][]Edge,
		currency string,
		amount float64,
		values map[string]float64,
	)

	dfs = func(
		graph map[string][]Edge,
		currency string,
		amount float64,
		values map[string]float64,
	) {
		values[currency] = amount

		for _, edge := range graph[currency] {
			if _, exists := values[edge.to]; !exists {
				dfs(
					graph,
					edge.to,
					amount*edge.rate,
					values,
				)
			}
		}
	}

	graph1 := buildGraph(pairs1, rates1)
	graph2 := buildGraph(pairs2, rates2)

	day1Values := make(map[string]float64)
	dfs(graph1, initialCurrency, 1.0, day1Values)

	day2Values := make(map[string]float64)
	dfs(graph2, initialCurrency, 1.0, day2Values)

	answer := 1.0

	for currency, amount := range day1Values {
		if value2, exists := day2Values[currency]; exists {
			finalAmount := amount / value2

			if finalAmount > answer {
				answer = finalAmount
			}
		}
	}

	return answer
}

The Go implementation closely mirrors the Python solution. The primary difference is the explicit Edge struct used to represent adjacency list entries.

Go requires explicit map existence checks using the exists boolean. Floating point values use float64, which is appropriate because the problem constraints guarantee the result remains within safe bounds.

Worked Examples

Example 1

initialCurrency = "EUR"

Day 1:

EUR -> USD = 2
USD -> JPY = 3

Day 2:

JPY -> USD = 4
USD -> CHF = 5
CHF -> EUR = 6

Day 1 Traversal

Currency	Amount
EUR	1
USD	2
JPY	6

Day 2 Traversal Starting From EUR

Reverse relationships are automatically included.

Currency	Value Relative to EUR
EUR	1
CHF	1/6
USD	1/30
JPY	1/120

Final Computation

Intermediate Currency	Day 1 Amount	Day 2 Value	Final Result
EUR	1	1	1
USD	2	1/30	60
JPY	6	1/120	720

Maximum = 720.

Example 2

initialCurrency = "NGN"

Day 1:

NGN -> EUR = 9

Day 2:

NGN -> EUR = 6

Day 1 Traversal

Currency	Amount
NGN	1
EUR	9

Day 2 Traversal

Currency	Value
NGN	1
EUR	6

Final Computation

Currency	Formula	Result
NGN	1 / 1	1
EUR	9 / 6	1.5

Maximum = 1.5.

Example 3

initialCurrency = "USD"

Day 1:

USD -> EUR = 1

Day 2:

EUR -> JPY = 10

No profitable return path exists back to USD on day 2.

Final Result

Best choice is no conversion.

Answer = 1.0.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(V + E)	Each graph traversal visits every node and edge once
Space	O(V + E)	Adjacency lists and visited maps

The graphs are very small, with at most around 20 currencies and 20 edges. DFS traversal is linear in graph size, making the solution extremely efficient.

Test Cases

sol = Solution()

# Example 1
assert abs(
    sol.maxAmount(
        "EUR",
        [["EUR", "USD"], ["USD", "JPY"]],
        [2.0, 3.0],
        [["JPY", "USD"], ["USD", "CHF"], ["CHF", "EUR"]],
        [4.0, 5.0, 6.0]
    ) - 720.0
) < 1e-5

# Example 2
assert abs(
    sol.maxAmount(
        "NGN",
        [["NGN", "EUR"]],
        [9.0],
        [["NGN", "EUR"]],
        [6.0]
    ) - 1.5
) < 1e-5

# Example 3
assert abs(
    sol.maxAmount(
        "USD",
        [["USD", "EUR"]],
        [1.0],
        [["EUR", "JPY"]],
        [10.0]
    ) - 1.0
) < 1e-5

# No conversions needed
assert abs(
    sol.maxAmount(
        "USD",
        [["USD", "EUR"]],
        [2.0],
        [["USD", "EUR"]],
        [2.0]
    ) - 1.0
) < 1e-5

# Multi-step profitable chain
assert abs(
    sol.maxAmount(
        "A",
        [["A", "B"], ["B", "C"]],
        [2.0, 3.0],
        [["C", "A"]],
        [10.0]
    ) - 60.0
) < 1e-5

# Disconnected graph on day 2
assert abs(
    sol.maxAmount(
        "USD",
        [["USD", "EUR"]],
        [5.0],
        [["JPY", "GBP"]],
        [2.0]
    ) - 1.0
) < 1e-5

# Single currency reachable
assert abs(
    sol.maxAmount(
        "AAA",
        [["AAA", "BBB"]],
        [4.0],
        [["BBB", "AAA"]],
        [2.0]
    ) - 8.0
) < 1e-5

# Identity conversion rates
assert abs(
    sol.maxAmount(
        "USD",
        [["USD", "EUR"]],
        [1.0],
        [["EUR", "USD"]],
        [1.0]
    ) - 1.0
) < 1e-5

Test Case Summary

Test	Why
Example 1	Validates long profitable conversion chain
Example 2	Verifies inverse conversion handling
Example 3	Ensures zero conversions are allowed
Equal rates both days	Confirms no false profit detection
Multi-step chain	Tests DFS multiplication propagation
Disconnected graphs	Ensures unreachable currencies are ignored
Simple profitable cycle	Verifies correct final multiplication
Identity rates	Tests neutral conversions

Edge Cases

One important edge case occurs when the optimal strategy is to perform no conversions at all. A naive implementation might assume at least one conversion must happen, but the problem explicitly allows zero conversions. The implementation handles this by initializing the answer to 1.0, which represents keeping the original currency unchanged.

Another important case involves disconnected graphs. A currency reachable on day 1 may not be reachable on day 2. Attempting to use such a currency as an intermediate step would be invalid because there is no path back to the initial currency. The implementation correctly handles this by checking whether the currency exists in both traversal maps before computing the final amount.

A third tricky case involves inverse exchange rates. Since every conversion pair implicitly supports the reverse direction using 1 / rate, forgetting to add reverse edges would make many valid paths unreachable. The graph construction explicitly inserts both directions, ensuring all legal conversions are represented.

Floating point precision can also become a source of bugs because repeated multiplication and division may accumulate rounding error. The implementation uses float in Python and float64 in Go, which provide sufficient precision for the problem constraints.